/[ascend]/trunk/ascend4/solver/mtx_perms.h
ViewVC logotype

Annotation of /trunk/ascend4/solver/mtx_perms.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (hide annotations) (download) (as text)
Fri Oct 29 20:54:12 2004 UTC (17 years, 8 months ago) by aw0a
File MIME type: text/x-chdr
File size: 20348 byte(s)
Setting up web subdirectory in repository
1 aw0a 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