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

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