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

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

Parent Directory Parent Directory | Revision Log Revision Log


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

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