/[ascend]/trunk/base/generic/solver/mtx_perms.h
ViewVC logotype

Contents of /trunk/base/generic/solver/mtx_perms.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations) (download) (as text)
Fri Oct 29 20:54:12 2004 UTC (17 years, 9 months ago) by aw0a
Original Path: trunk/ascend4/solver/mtx_perms.h
File MIME type: text/x-chdr
File size: 20348 byte(s)
Setting up web subdirectory in repository
1 /*
2 * mtx: Ascend Sparse Matrix Package
3 * by Benjamin Andrew Allan
4 * Derived from mtx by Karl Michael Westerberg
5 * Created: 5/3/90
6 * Version: $Revision: 1.10 $
7 * Version control file: $RCSfile: mtx_perms.h,v $
8 * Date last modified: $Date: 1998/05/06 17:28:54 $
9 * Last modified by: $Author: ballan $
10 *
11 * This file is part of the SLV solver.
12 *
13 * Copyright (C) 1996 Benjamin Andrew Allan
14 *
15 * The SLV solver is free software; you can redistribute
16 * it and/or modify it under the terms of the GNU General Public License as
17 * published by the Free Software Foundation; either version 2 of the
18 * License, or (at your option) any later version.
19 *
20 * The SLV solver is distributed in hope that it will be
21 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 * General Public License for more details.
24 *
25 * You should have received a copy of the GNU General Public License along with
26 * the program; if not, write to the Free Software Foundation, Inc., 675
27 * Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING.
28 * COPYING is found in ../compiler.
29 */
30 #ifndef __MTX_PERMS_H_SEEN__
31 #define __MTX_PERMS_H_SEEN__
32 /* requires #include "mtx.h" */
33
34
35 /* the following block_perm functions are not yet implemented: this is
36 the software spec. 5/3/95 baa. */
37
38 extern mtx_block_perm_t mtx_create_block_perm(mtx_matrix_t);
39 /**
40 *** bp = mtx_create_block_perm(mtx);
41 *** mtx_matrix_t mtx;
42 *** mtx_block_perm_t bp;
43 ***
44 *** Returns a token with the permutation/block information of the
45 *** mtx given. The mtx given must be previously output assigned and,
46 *** if it is to be partitioned, should already be partitioned.
47 *** The permutation returned can be used subsequently in various
48 *** ways, but all operations must be on the mtx the data came from.
49 *** If the matrix is reoutput assigned or repartitioned, the data
50 *** in bp becomes (potentially) invalid and should be completely
51 *** updated with mtx_update_block_perm.
52 *** Returns NULL if a bad mtx is detected.
53 ***
54 *** Passes calls on slave matrices up to the master matrix.
55 ***
56 -$- Checks extra carefully for a bad matrix, and returns NULL if so.
57 **/
58
59 extern int mtx_update_block_perm(mtx_matrix_t,
60 int32, mtx_block_perm_t);
61 /**
62 *** mtx_update_block_perm(mtx,bnum,bperm);
63 *** mtx_matrix_t mtx;
64 *** int32 bnum;
65 *** mtx_block_perm_t bperm;
66 ***
67 *** Given an mtx, a block number, and an existing bperm, this
68 *** routine updates the bperm permutation information about the
69 *** block bnum in the mtx.
70 *** The bperm updated must come from the mtx the bperm was created
71 *** for. The mtx must be output assigned and, if the mtx was
72 *** partitioned, the partition data must be consistent between the
73 *** bperm and the mtx. The mtx cannot have been resized.
74 ***
75 *** Exceptions: If bnum is mtx_ALL_BLOCKS, we check only for the
76 *** mtx identity and output assignment. All previous permutation and
77 *** block information is ignored and replace by current info.
78 *** Calling with mtx_ALL_BLOCKS is substantially more expensive
79 *** than calling with a specific block number unless the block is
80 *** nearly the size of the problem.
81 ***
82 *** Passes calls on slave matrices up to the master matrix.
83 ***
84 *** Returns 1 from a bad matrix, 2 from a bad bperm, 3 from a mismatch.
85 *** Returns 0 from a successful call.
86 ***
87 -$- Does excessive result checking, and then returns 3 if the
88 -$- excessive checks fail.
89 **/
90
91 extern int mtx_restore_block_perm(mtx_matrix_t, int32,
92 mtx_block_perm_t);
93 /**
94 *** mtx_restore_block_perm(mtx,bnum,bperm);
95 *** mtx_matrix_t mtx;
96 *** int32 bnum;
97 *** mtx_block_perm_t bperm;
98 ***
99 *** Given an mtx, a block number, and an existing bperm, this
100 *** routine updates the mtx permutation information for the
101 *** block bnum using the bperm.
102 *** The mtx updated must go with the bperm.
103 *** The mtx must be output assigned and, if the mtx was
104 *** partitioned, the partition data must be consistent between the
105 *** bperm and the mtx. The mtx cannot have been resized.
106 *** The parity of the mtx will be set to that stored with the bperm;
107 *** if you try to do sneaky things, parity may get out of whack.
108 ***
109 *** Exceptions: If bnum is mtx_ALL_BLOCKS, we check only for the
110 *** mtx identity and order. All previous permutation and
111 *** block information is ignored and replaced by bperm info.
112 *** The mtx's output_assigned and partition characteristics will
113 *** be restored to their values at the time the bperm was last
114 *** created or updated.
115 *** Calling with mtx_ALL_BLOCKS is substantially more expensive
116 *** than calling with a specific block number if all you really
117 *** want updated is a specific block.
118 ***
119 *** Passes calls on slave matrices up to the master matrix.
120 ***
121 *** Returns 1 from a bad matrix, 2 from a bad bperm, 3 from a mismatch.
122 *** Returns 0 from a successful call.
123 ***
124 -$- Does excessive checking, and then returns usual values if the
125 -$- corresponding excessive checks fail.
126 **/
127
128 extern int mtx_destroy_block_perm(mtx_block_perm_t);
129 /**
130 *** mtx_destroy_block_perm(bperm);
131 *** mtx_block_perm_t bperm;
132 ***
133 *** Deallocates all memory associated with the bperm.
134 *** Has nothing to do with the matrix of bperm's origin.
135 *** Returns 1 if anything untoward happens during the
136 *** destruction. Returns 0 otherwise.
137 **/
138
139 extern size_t mtx_block_perm_size(mtx_block_perm_t);
140 /**
141 *** mtx_block_perm_size(bperm);
142 *** mtx_block_perm_t bperm;
143 ***
144 *** One for the bean counters. Returns current memory used by
145 *** the mtx_block_perm_t. Bytes as usual.
146 **/
147
148 /* end block_perm functions */
149
150 /***********************************************************************\
151 mtx permutation and permutation info routines
152 \***********************************************************************/
153 extern void mtx_swap_rows(mtx_matrix_t, int32, int32);
154 extern void mtx_swap_cols(mtx_matrix_t, int32, int32);
155 extern void mtx_drag(mtx_matrix_t, int32, int32);
156 extern void mtx_reverse_diagonal(mtx_matrix_t,
157 int32, int32);
158 /**
159 -$- mtx_swap_rows(matrix,row1,row2)
160 -$- mtx_swap_cols(matrix,col1,col2)
161 -$- mtx_drag(matrix,d1,d2)
162 -$- mtx_reverse_diagonal(matrix,d1,d2)
163 *** mtx_matrix_t matrix;
164 *** int32 row1,row2;
165 *** int32 col1,col2;
166 *** int32 d1,d2;
167 ***
168 *** Swaps two rows/columns of the matrix. The association between the
169 *** "original row/column number" and the row/column contents is not
170 *** changed, so that some record is kept as to where a given row/column
171 *** originally came from (see mtx_org_to_row, etc.).
172 ***
173 *** Drag shifts diagonal element d1 to position d2, or vice versa,
174 *** rotating all the intermediate elements as if d1 were swapped
175 *** (row and col) with all the intermediate di.
176 *** Drag exists because it is twice the speed of the following
177 *** implementation outside of mtx:
178 *** while( n1 < n2 ) {
179 *** mtx_swap_rows(mtx,n1,n1+1);
180 *** mtx_swap_cols(mtx,n1,n1+1);
181 *** ++n1;
182 *** }
183 *** while( n1 > n2 ) {
184 *** mtx_swap_rows(mtx,n1,n1-1);
185 *** mtx_swap_cols(mtx,n1,n1-1);
186 *** --n1;
187 *** }
188 *** If it turns out that a cycle_col or cycle_row (independent of diagonal)
189 *** is wanted, implementation is now trivial.
190 ***
191 *** Reverse_diagonal does a series of symmetric permutations that reverses
192 *** the ordering of the diagonal between (and including) d1 & d2.
193 *** If d2 < d1, does nothing.
194 ***
195 *** All pass calls on slave matrices up to the master matrix.
196 ***
197 -$- Does nothing to a bad matrix.
198 **/
199
200 extern int32 mtx_row_to_org(mtx_matrix_t, int32);
201 extern int32 mtx_col_to_org(mtx_matrix_t, int32);
202 extern int32 mtx_org_to_row(mtx_matrix_t, int32);
203 extern int32 mtx_org_to_col(mtx_matrix_t, int32);
204 /**
205 -$- org_row = mtx_row_to_org(matrix,row)
206 -$- org_col = mtx_col_to_org(matrix,col)
207 -$- row = mtx_org_to_row(matrix,org_row)
208 -$- col = mtx_org_to_col(matrix,org_col)
209 *** int32 org_row,row,org_col,col;
210 *** mtx_matrix_t matrix;
211 ***
212 *** Converts original row number <--> row number, and original column
213 *** number <--> column number.
214 *** All pass calls on slave matrices up to the master matrix.
215 ***
216 -$- Returns -1 from a bad matrix.
217 **/
218
219 extern boolean mtx_row_parity(mtx_matrix_t);
220 extern boolean mtx_col_parity(mtx_matrix_t);
221 /**
222 -$- parity = mtx_row_parity(matrix)
223 -$- parity = mtx_col_parity(matrix)
224 *** boolean parity;
225 *** mtx_matrix_t matrix;
226 ***
227 *** Returns the parity (even=FALSE,odd=TRUE) of the permutation which
228 *** carries original row/column to current row/column numbers.
229 *** All pass calls on slave matrices up to the master matrix.
230 ***
231 -$- Returns -1 from a bad matrix.
232 **/
233
234 /***********************************************************************\
235 mtx structural manipulation and info routines
236 \***********************************************************************/
237
238 extern int mtx_output_assign_region(mtx_matrix_t, mtx_region_t *,int *);
239 /**
240 *** int rank = mtx_output_assign_region(matrix,region,orphaned_rows)
241 *** mtx_matrix_t matrix;
242 *** mtx_region_t *reg;
243 *** int orphaned_rows;
244 ***
245 *** This function is very similar to its sister function mtx_output_assign.
246 *** It reorders the matrix to put as many non-zeros on the diagonal as
247 *** possible. It mtx_ENTIRE_MATRIX is sent in as the region, the output
248 *** assignment will affect the entire matrix. Otherwise the output
249 *** assignment will be restricted to the designated region.
250 *** This function returns the symbolic rank of the matrix. If a row can
251 *** not be assigned it is moved to the end of lower edge of the matrix.
252 *** The count of the unassigned aka orphaned rows is returned also.
253 *** Unlike mtx_output_assign nothing else is done to the matrix.
254 ***
255 *** Calls on slaves are passed up to the master matrix.
256 ***
257 -$- Does nothing to a bad matrix.
258 **/
259
260
261 extern void mtx_output_assign(mtx_matrix_t, int32, int32);
262 /**
263 *** mtx_output_assign(matrix,hirow,hicol)
264 *** mtx_matrix_t matrix;
265 *** int32 hirow,hicol;
266 ***
267 *** Reorders the matrix to put as many non-zeros on the diagonal as
268 *** possible. This function does not assume the validity of a previous
269 *** assignment. mtx_symbolic_rank() may be subsequently called to produce
270 *** the symbolic rank. All assigned rows and columns go into forming
271 *** a single initial block which is of dimension equal to the symbolic
272 *** rank of the matrix.
273 ***
274 *** All unassigned rows and columns with incidence are then placed
275 *** against the borders of the nonsingular region while all empty rows
276 *** and columns are moved toward the outer borders of the matrix.
277 *** If hirow and hicol are not improperly small, we will guarantee that all
278 *** original rows r, 0 <= r < hirow, and original columns c,
279 *** 0 <= c < hicol, are placed next to the initial block. That is,
280 *** if that block is contained within the block ((0,0),(hirow,hicol)).
281 *** This is not a particularly interesting property mathematically, but
282 *** it makes things loads easier when writing interfaces that involve
283 *** mtx objects; the first hirow rows and hicol cols of the jacobian will
284 *** correspond to some relation or variable even if they haven't incidence.
285 -$- Does nothing to a bad matrix.
286 *** NOTE:
287 *** When used on an incidence matrix, the fixed vars and unincluded
288 *** relations which don't generate elements may end up anywhere between
289 *** the initial block and the ends of the matrix if hirow and hicol are
290 *** not specified correctly.
291 ***
292 *** Calls on slaves are passed up to the master matrix.
293 ***
294 *** Note that mtx_output_assign invalidates any data saved
295 *** with the mtx_*_block_perm functions.
296 **/
297
298 extern boolean mtx_output_assigned(mtx_matrix_t);
299 /**
300 *** symbolic_rank_exists = mtx_output_assigned(matrix)
301 *** boolean symbolic_rank_exists;
302 *** mtx_matrix_t matrix;
303 ***
304 *** Determines if the matrix has been previously output assigned.
305 *** Calls on slaves are passed up to the master matrix.
306 ***
307 -$- Returns FALSE on a bad matrix.
308 **/
309
310 extern int32 mtx_symbolic_rank(mtx_matrix_t);
311 /**
312 *** symbolic_rank = mtx_symbolic_rank(matrix)
313 *** int32 symbolic_rank;
314 *** mtx_matrix_t matrix;
315 ***
316 *** Returns the symbolic rank determined by a previous call to
317 *** mtx_output_assign().
318 *** Calls on slaves are passed up to the master matrix.
319 ***
320 -$- Returns -2 on bad matrix or -1 on unassigned one.
321 **/
322
323 extern void mtx_set_symbolic_rank(mtx_matrix_t, int32);
324 /**
325 *** mtx_symbolic_rank(matrix,rank)
326 *** int32 rank;
327 *** mtx_matrix_t matrix;
328 ***
329 *** Sets symbolic rank of mtx. This is used in a hack
330 *** and is not intended for general use.
331 ***
332 **/
333
334 extern boolean mtx_make_col_independent(mtx_matrix_t,int32,
335 mtx_range_t *);
336 /**
337 *** swapped = mtx_make_col_independent(matrix,col,rng)
338 *** boolean swapped;
339 *** mtx_matrix_t matrix;
340 *** int32 col;
341 *** mtx_range_t *rng;
342 ***
343 *** Removes col from the basis in place of one of the columns in rng.
344 *** I.e. redoes the mtx_output_assign so as to not use col, if
345 *** possible, using one of the cols in rng instead.
346 *** Clears any prior partitioning data.
347 *** Note that mtx_make_col_independent invalidates any data saved
348 *** with the mtx_*_block_perm functions.
349 ***
350 *** Calls on slaves are passed up to the master matrix.
351 **/
352
353
354 extern void mtx_org_permute(mtx_matrix_t, mtx_region_t *);
355 /**
356 *** mtx_org_permute(mtx,region);
357 *** mtx_matrix_t matrix;
358 *** mtx_region_t *region.
359 ***
360 *** Given a region, repermutes rows and columns within it to the ordering
361 *** where mtx_row_to_org(mtx,i) < mtx_row_to_org(mtx,i+1) for all i and
362 *** where mtx_col_to_org(mtx,j) < mtx_row_to_org(mtx,j+1) for all j
363 *** within the region. At present this is implemented as a qsort and
364 *** may be a little pricey.
365 ***
366 *** mtx_org_permute(mtx,mtx_ENTIRE_MATRIX); is equivalent to
367 *** mtx_reset_perm(mtx);
368 **/
369
370 extern int32 mtx_full_diagonal(mtx_matrix_t, mtx_range_t *, int);
371 /**
372 *** mtx_full_diagonal(mtx,rng,noisy);
373 ***
374 *** This function checks the diagonal for holes. If symbolic_rank is
375 *** set, and rng->high < rank, returns immediately.
376 *** Returns number of holes detected in diagonal in rng given.
377 *** If noisy != 0, writes the hole locations to g_mtxerr.
378 *** On detectably bad input, returns -1.
379 *** Worst Cost: O(nnz) where nnz = incidence count sum over rows in rng.
380 *** Usual Cost: O(n) where n = a small factor *(rng->high - rng->low +1)
381 *** Does not pass calls up to master.
382 **/
383
384 extern int32 mtx_transpose(mtx_matrix_t);
385 /**
386 *** mtx_transpose(mtx);
387 *** Transposes everything about the matrix. The user is
388 *** responsible for keeping track of the change in the semantics
389 *** this implies if the matrix is being used in a nonlinear context.
390 ***
391 *** Transposing a matrix also transposes all associated slave/master
392 *** matrices.
393 *** To check if a matrix has been transposed, use mtx_isa_transpose.
394 *** Cost O(Nnz).
395 *** 0 order matrices cannot be transposed.
396 -$- Returns mtx_NONE on a bad or 0 order matrix.
397 **/
398
399 extern int32 mtx_isa_transpose(mtx_matrix_t);
400 /**
401 *** mtx_isa_transpose(mtx);
402 *** Returns 1 if the matrix is transposed from another and 0 if not.
403 *** Calling mtx_transpose twice yields a mtx which responds with 0.
404 -$- Returns mtx_NONE on a bad or 0 order matrix.
405 **/
406
407 /***********************************************************************\
408 Start of some block matrix routines. At the moment the block
409 structure is intimately tied up with the matrix.
410 \***********************************************************************/
411
412 extern mtx_block_t *mtx_block_partition(mtx_matrix_t, mtx_region_t *);
413 /**
414 *** mtx_partition(mtx,reg);
415 *** mtx_matrix_t matrix;
416 *** mtx_region_t *reg.
417 ***
418 *** Partitions the single block of a previously output assigned matrix
419 *** into smaller blocks if possible. This function unlike its sister
420 *** mtx_partition, takes in, and returns information explicitly, rather
421 *** than assuming it to be a property of the matrix. The result will
422 *** be NULL, if there are no blocks. At the moment works only on
423 *** a square matrix. The range reg->row is assumed to represent the
424 *** extreme points of a square region. The caller owns the result and
425 *** must be deallocate it.
426 *** If the matrix given (or its master) is not assigned, this will
427 *** verify (at some expense) that the diagonal is full and whine
428 *** if not. It will attempt to partition anyway assuming a diagonal.
429 ***
430 *** Calls on slaves are passed up to the master matrix.
431 **/
432
433
434 /***********************************************************************\
435 The original block manipulation routines.
436 \***********************************************************************/
437
438 extern void mtx_partition(mtx_matrix_t);
439 /**
440 *** mtx_partition(matrix);
441 *** mtx_matrix_t matrix;
442 ***
443 *** Takes an output assigned matrix and does a permutation to
444 *** block-lower-triangular form of the square region from
445 *** 0,0 to symbolic_rank-1, symbolic_rank-1.
446 ***
447 *** Calls on slaves are passed up to the master matrix.
448 **/
449
450 extern void mtx_ut_partition(mtx_matrix_t);
451 /**
452 *** mtx_ut_partition(matrix);
453 *** mtx_matrix_t matrix;
454 ***
455 *** Takes an output assigned matrix and does a permutation to
456 *** block-UPPER-triangular form of the square region from
457 *** 0,0 to symbolic_rank-1, symbolic_rank-1.
458 ***
459 *** Calls on slaves are passed up to the master matrix.
460 **/
461
462 extern boolean mtx_check_blocks(mtx_matrix_t);
463 /**
464 *** valid = mtx_check_blocks(matrix)
465 *** boolean valid;
466 *** mtx_matrix_t matrix;
467 ***
468 *** Checks whether or not the block data are consistent with the
469 *** non-zero structure of the matrix. If not, the block data
470 *** are destroyed. Matrix must be previously output assigned,
471 *** if not (or bad matrix) nothing is done.
472 ***
473 *** Calls on slaves are passed up to the master matrix.
474 **/
475
476 extern int32 mtx_number_of_blocks(mtx_matrix_t);
477 /**
478 ***
479 -$- nblocks = mtx_number_of_blocks(matrix)
480 *** int32 nblocks;
481 *** mtx_matrix_t matrix;
482 ***
483 *** Returns the number of blocks in the matrix. Matrix must be
484 *** previously output assigned.
485 ***
486 *** Calls on slaves are passed up to the master matrix.
487 ***
488 -$- Returns mtx_NONE if matrix is bad which is liable to lead to core
489 -$- dumping if the user is not checking for a bad return.
490 **/
491
492 extern int32 mtx_block(mtx_matrix_t,int32, mtx_region_t *);
493 /**
494 *** bndx = mtx_block(matrix,block_number,block)
495 *** mtx_matrix_t matrix;
496 *** int32 block_number;
497 *** mtx_region_t *block;
498 ***
499 *** Sets block to the "block_number"-th block (indexed 0 to nblocks-1) in
500 *** the matrix. Matrix must be previously output assigned.
501 *** Returns mtx_NONE if not previously output assigned
502 *** or if requested block does not exist, or if no blocks exist,
503 *** otherwise returns 0.
504 *** If mtx_NONE is returned, block will contain the region
505 *** ((0,order-1),(0,order-1)) where order is the mtx_order.
506 ***
507 *** Calls on slaves are passed up to the master matrix.
508 **/
509
510 extern int32 mtx_block_containing_row(mtx_matrix_t,int32,
511 mtx_region_t *);
512 extern int32 mtx_block_containing_col(mtx_matrix_t,int32,
513 mtx_region_t *);
514 /**
515 *** block_number = mtx_block_containing_row(matrix,row,block)
516 *** block_number = mtx_block_containing_col(matrix,col,block)
517 *** int32 block_number;
518 *** mtx_matrix_t matrix;
519 *** int32 row,col;
520 *** mtx_region_t *block;
521 ***
522 *** Sets block to the block which contains the given row/column and
523 *** returns the block number. If the given row/column doesn't belong
524 *** to any block, mtx_NONE is returned. Matrix must be previously output
525 *** assigned or a 0 is returned.
526 ***
527 *** Calls on slaves are passed up to the master matrix.
528 **/
529
530 #endif /* __MTX_PERMS_H_SEEN__ */

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22