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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1014 - (show annotations) (download) (as text)
Wed Jan 3 04:49:17 2007 UTC (15 years, 11 months ago) by johnpye
File MIME type: text/x-chdr
File size: 24512 byte(s)
Fixing @addtogroup comments
1 /* ASCEND modelling environment
2 Copyright (C) 1996 Benjamin Andrew Allan
3 Copyright (C) 2006 Carnegie Mellon University
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 mtx2: Ascend Sparse Matrix Package.
21 Requires:
22 #include "utilities/ascConfig.h"
23 #include "mtx.h"
24 *//*
25 mtx by Karl Michael Westerberg, created 5/3/90
26 mtx2 by Benjamin Andrew Allan
27 Last in CVS: $Revision: 1.9 $ $Date: 1997/07/18 12:15:12 $ $Author: mthomas $
28 */
29
30 #ifndef __MTX_QUERY_H_SEEN__
31 #define __MTX_QUERY_H_SEEN__
32
33 /** @addtogroup linear
34 Linear solver routines
35 @{ */
36
37 ASC_DLLSPEC(real64 ) mtx_next_in_row(mtx_matrix_t matrix,
38 mtx_coord_t *coord,
39 mtx_range_t *colrng);
40 /**< See mtx_next_in_col(), switching row & column references. */
41 extern real64 mtx_next_in_col(mtx_matrix_t matrix,
42 mtx_coord_t *coord,
43 mtx_range_t *rowrng);
44 /**<
45 *** Searches for the next non-zero in the given row, whose column index
46 *** lies in the given range, and returns its value. Coord->col is set to
47 *** the column in which it was found. To find the first non-zero in the
48 *** row, set coord->col = mtx_FIRST. Coord->col will equal mtx_LAST and
49 *** 0.0 will be returned if there is no next non-zero. The row (and mtx!)
50 *** searched is always the one specified when mtx_next_in_row was most
51 *** recently called with a coord such that coord->col == mtx_FIRST.
52 *** If colrng.low > colrng.high, return is mtx_LAST, which gives correct
53 *** behaviour for mtx/vector processing loops.
54 *** If nz.row is not in the matrix (<0 || >= mtx order) on an initial
55 *** call (with nz.col == mtx_FIRST) returns 0.0 and nz.col == mtx_LAST.
56 ***
57 *** Example of canonical usage: <pre>
58 *** nz.col = col; (* the col to be traversed *)
59 *** nz.row = mtx_FIRST; (* initializer, which must be used *)
60 *** while( value = mtx_next_in_col(mtx,&nz,rowrng)),
61 *** nz.row != mtx_LAST ) { (* your thing here *) } </pre>
62 *** Note that the logic test of the while is ONLY nz.row != mtx_LAST.
63 *** C lets you do whatever you choose before the comma.<br><br>
64 ***
65 -$- Returns FALSE from bad a matrix.<br><br>
66 ***
67 *** NOTE: The notion of "next non-zero" is arbitrary, but will not change
68 *** until the next destructive operation on the matrix is performed.
69 *** Neither the row/col number nor the rel/var index will
70 *** behave monotonically while traversing a col/row. This means there
71 *** is nothing you can do with the range to shrink the search space
72 *** based on the last row/col returned. Basic matrix operations, when
73 *** properly thought about in a general sparse context, do not care
74 *** about the order in which the elements of vectors are processed.
75 *** <pre>
76 *** WARNINGS:
77 !1! - You may NOT nest mtx_next_in_col within mtx_next_in_col
78 ! ! or mtx_next_in_row within mtx_next_in_row. We have yet to find a
79 ! ! process suggestive of doing so that was not better handled with
80 ! ! a for loop. This is a global constraint. Violation results in garbage.
81 !2! - You may NOT safely perform operation mtx_del_zr_in_col while traversing
82 ! ! a column unless the value just returned from the previous next_in_col is
83 ! ! nonzero or the coord.row last returned is mtx_LAST. Also, you may NOT
84 ! ! safely perform operation mtx_del_zr_in_row on coord.row unless the
85 ! ! value just returned from the previous next_in_col is nonzero.
86 ! ! The proscription here is for mtx_next_in_ and mtx_del_zr_in_ operating
87 ! ! on the same matrix. mtx_del_zr_in_ is safe to call if the mtx_next_in_
88 ! ! driving it is happening on a different matrix.
89 !3! Transpose warning 2 for next_in_row.
90 ! ! Violation of 2 or 3 results, sooner or later, in a memory fault.
91 *** You CAN nest mtx_next_in_col within mtx_next_in_row or vice versa,
92 *** however.
93 *** </pre>
94 **/
95
96 extern real64 mtx_row_max(mtx_matrix_t matrix,
97 mtx_coord_t *coord,
98 mtx_range_t *colrng,
99 real64 *signval);
100 /**< See mtx_col_max(), switching row & column references. */
101 extern real64 mtx_col_max(mtx_matrix_t matrix,
102 mtx_coord_t *coord,
103 mtx_range_t *rowrng,
104 real64 *signval);
105 /**<
106 *** Searches for the element in the given row, with column index in the
107 *** given column range, which has the largest absolute value. The user
108 *** should set coord->row to the desired row to search, and this function
109 *** will set coord->col to the column index where the maximum was found
110 *** (or mtx_NONE if no non-zero was found in that range). The absolute
111 *** value of that element is also returned. If the pointer signval is not
112 *** NULL, the real64 pointed to will be stuffed with the signed
113 *** value of the maximum sized element.
114 *** In the event of ties, the element with the lowest current column
115 *** index wins.
116 ***
117 -$- Returns -1.0 from a bad matrix.
118 **/
119 extern real64 mtx_row_min(mtx_matrix_t matrix,
120 mtx_coord_t *coord,
121 mtx_range_t *colrng,
122 real64 *signval,
123 real64 minval);
124 /**< See mtx_col_min(), switching row & column references. */
125 extern real64 mtx_col_min(mtx_matrix_t matrix,
126 mtx_coord_t *coord,
127 mtx_range_t *rowrng,
128 real64 *signval,
129 real64 minval);
130 /**<
131 *** Searches for the element in the given row, with column index in the
132 *** given column range, which has the smallest absolute value. The user
133 *** should set coord->row to the desired row to search, and this function
134 *** will set coord->col to the column index where the minimum was found
135 *** (or mtx_NONE if no non-zero was found in that range). The absolute
136 *** value of that element is also returned. If the pointer signval is not
137 *** NULL, the real64 pointed to will be stuffed with the signed
138 *** value of the minimum sized element.
139 *** In the event of ties, the element with the lowest current column
140 *** index wins.<br><br>
141 *** This function only looks at the nonzero elements, and will only
142 *** find numbers between minval and 1e50. If no number is found signval
143 *** will be zero and
144 *** value will be one.<br><br>
145 ***
146 -$- Returns -1.0 from a bad matrix.
147 **/
148
149 extern real64 mtx_get_pivot_col(mtx_matrix_t matrix,
150 mtx_coord_t *coord,
151 mtx_range_t *colrng,
152 real64 *signval,
153 real64 tol,
154 real64 eps);
155 /**< See mtx_get_pivot_row(), switching row & column references. */
156 extern real64 mtx_get_pivot_row(mtx_matrix_t matrix,
157 mtx_coord_t *coord,
158 mtx_range_t *rowrng,
159 real64 *signval,
160 real64 tol,
161 real64 eps);
162 /**<
163 *** This implements efficiently the standard sparse modification
164 *** of LU partial pivot selection.
165 ***
166 *** Searches for the leftmost element in the colrng of the given row,
167 *** which passes the sparse partial pivoting criteria:
168 *** -# aij >= eps,
169 *** -# aij >= tol * max_abs_element_value_in_colrng.
170 *** The absolute value of the passing element is returned, or 0.0 if
171 *** there are no entries that pass criterion 1. The user
172 *** should set coord->row to the desired row to search. This function
173 *** will set coord->col to the column index where the result was found
174 *** (or mtx_NONE if nothing good was found in that range). The absolute
175 *** value of that element is also returned. If the pointer signval is not
176 *** NULL, the real64 pointed to will be stuffed with the signed
177 *** value of the selected element.
178 *** This function is faster when colrng == mtx_ALL_COLS can be used.<br><br>
179 ***
180 -$- Returns -1.0 from a bad matrix.
181 **/
182
183 extern int32 mtx_nonzeros_in_row(mtx_matrix_t matrix,
184 int32 row,
185 mtx_range_t *colrng);
186 /**<
187 *** Counts the number of incidences in the given row whose column index
188 *** lies in the given column range.
189 -$- Returns -1 from a bad matrix.
190 **/
191 extern int32 mtx_nonzeros_in_col(mtx_matrix_t matrix,
192 int32 col,
193 mtx_range_t *rowrng);
194 /**<
195 *** Counts the number of incidences in the given column whose row index
196 *** lies in the given row range.
197 -$- Returns -1 from a bad matrix.
198 **/
199 extern int32 mtx_nonzeros_in_region(mtx_matrix_t matrix,
200 mtx_region_t *reg);
201 /**<
202 *** Counts the non-zero values in the given region.
203 -$- Returns -1 from a bad matrix.
204 **/
205 extern int32 mtx_numbers_in_row(mtx_matrix_t matrix,
206 int32 row,
207 mtx_range_t *colrng);
208 /**<
209 *** Counts the non-zero values in the given row whose column index
210 *** lies in the given column range.
211 -$- Returns -1 from a bad matrix.
212 **/
213 extern int32 mtx_numbers_in_col(mtx_matrix_t matrix,
214 int32 col,
215 mtx_range_t *rowrng);
216 /**<
217 *** Counts the non-zero values in the given column whose row index
218 *** lies in the given row range.
219 -$- Returns -1 from a bad matrix.
220 **/
221 extern int32 mtx_numbers_in_region(mtx_matrix_t matrix,
222 mtx_region_t *reg);
223 /**<
224 *** Counts the number of incidences in the given region.
225 -$- Returns -1 from a bad matrix.
226 **/
227
228 /* ********************************************************************* *\
229 mtx vector operation routines
230 None of these routines care about master/slave status.
231 \* ********************************************************************* */
232
233 /* *************************************************************** *\
234 Dense vector operations, rather analogous to the mtx_value suite.
235 These are tools for data motion. No dense-dense arithmetic operators
236 are provided as these are best left to the user to design or steal
237 from elsewhere, e.g. blas. The (de)allocation of dense vectors is
238 the user's job,as is insuring that the dense vectors used are
239 large enough to accomodate operations in the range of the given
240 mtx_range_t. mtx->order is a safe size to use if you can't think
241 of something else.
242 \* *************************************************************** */
243
244 extern void mtx_org_row_vec(mtx_matrix_t mtx, int32 row,
245 real64 *vec, mtx_range_t *colrng);
246 /**< See mtx_cur_col_vec(), switching row & column references. */
247 ASC_DLLSPEC(void ) mtx_org_col_vec(mtx_matrix_t mtx, int32 col,
248 real64 *vec, mtx_range_t *rowrng);
249 /**< See mtx_cur_col_vec(). */
250 extern void mtx_cur_row_vec(mtx_matrix_t mtx, int32 row,
251 real64 *vec, mtx_range_t *colrng);
252 /**< See mtx_cur_col_vec(), switching row & column references. */
253 extern void mtx_cur_col_vec(mtx_matrix_t mtx, int32 col,
254 real64 *vec, mtx_range_t *rowrng);
255 /**<
256 *** The user is expected to supply the vec; we cannot check it.
257 *** Copies the mtx nonzeros currently within rowrng INTO array vec which is
258 *** indexed by org/cur row number. Does not affect other
259 *** entries of vec in or outside the range. In particular, vec
260 *** is NOT zeroed within the range unless there is a matrix element
261 *** with value zero at that location.<br><br>
262 ***
263 *** Notes: It is faster to call this with mtx_ALL_COLS/ROWS when
264 *** the row/col of interest is known to have incidence exclusively in
265 *** the range of interest.<br><br>
266 ***
267 -$- Fetches nothing from a bad matrix.
268 **/
269
270 /* *************************************************************** *\
271 Sparse vector operations, rather analogous to the mtx_value suite.
272 These are tools for data motion. No arithmetic operators
273 are provided as yet. The deallocation of sparse vectors is
274 the user's job. See the notes at the top of this header for the
275 data semantics of a sparse vector.
276 The user may construct a sparse vector.
277 Calls which return a sparse vector may create or use and return
278 a user supplied sparse vector. These calls are at liberty to
279 reallocate the data memory if that supplied is insufficient to
280 hold the data. The len and cap values of the vector will be reset
281 as appropriate.
282
283 Functions do not create a sparse unless it says in their header
284 that mtx_CREATE_SPARSE is a valid argument.
285 \* *************************************************************** */
286
287 extern mtx_sparse_t *mtx_org_row_sparse(mtx_matrix_t mtx,
288 int32 row,
289 mtx_sparse_t * const sparse,
290 mtx_range_t *colrng,
291 int zeroes);
292 /**< See mtx_cur_col_sparse(), switching row & column references. */
293 extern mtx_sparse_t *mtx_org_col_sparse(mtx_matrix_t mtx,
294 int32 col,
295 mtx_sparse_t * const sparse,
296 mtx_range_t *rowrng,
297 int zeroes);
298 /**< See mtx_cur_col_sparse(). */
299 extern mtx_sparse_t *mtx_cur_row_sparse(mtx_matrix_t mtx,
300 int32 row,
301 mtx_sparse_t * const sparse,
302 mtx_range_t *colrng,
303 int zeroes);
304 /**< See mtx_cur_col_sparse(), switching row & column references. */
305 extern mtx_sparse_t *mtx_cur_col_sparse(mtx_matrix_t mtx,
306 int32 col,
307 mtx_sparse_t * const sparse,
308 mtx_range_t *rowrng,
309 int zeroes);
310 /**<
311 *** Copies the mtx nonzeros currently within rowrng to the sparse,
312 *** indexing by org/cur row number. Nonzeros with value 0.0 WILL
313 *** be included in the sparse iff zeros is mtx_SOFT_ZEROES.
314 *** sparse->len will be set accordingly.
315 ***
316 *** The user must supply the sparse. It will not be enlarged.
317 *** mtx_CREATE_SPARSE is not a valid argument.
318 *** If capacity of the sparse given is insufficient, we will
319 *** copy as much data as will fit into sparse and return NULL.
320 *** User beware!<br><br>
321 ***
322 *** Notes: It is faster to call this with mtx_ALL_COLS/ROWS when
323 *** the row/col of interest is known to have incidence exclusively in
324 *** the range of interest.<br><br>
325 ***
326 -$- Fetches nothing from a bad matrix.
327 **/
328
329 extern void mtx_zr_org_vec_using_row(mtx_matrix_t mtx, int32 row,
330 real64 *vec, mtx_range_t *colrng);
331 /**< See mtx_zr_cur_vec_using_col(), switching row & column references. */
332 ASC_DLLSPEC(void ) mtx_zr_org_vec_using_col(mtx_matrix_t mtx, int32 col,
333 real64 *vec, mtx_range_t *rowrng);
334 /**< See mtx_zr_cur_vec_using_col(). */
335 extern void mtx_zr_cur_vec_using_row(mtx_matrix_t mtx, int32 row,
336 real64 *vec, mtx_range_t *colrng);
337 /**< See mtx_zr_cur_vec_using_col(), switching row & column references. */
338 extern void mtx_zr_cur_vec_using_col(mtx_matrix_t mtx, int32 col,
339 real64 *vec, mtx_range_t *rowrng);
340 /**<
341 *** Sets the values of vec (indexed by org/cur col) corresponding to
342 *** incidences in rowrng to 0.0.<br><br>
343 ***
344 *** Notes: It is faster to call this with mtx_ALL_COLS/ROWS when
345 *** practical, and the org flavor is faster than the cur flavor.<br><br>
346 ***
347 -$- Does nothing given a bad matrix.
348 **/
349
350 extern real64 mtx_sum_sqrs_in_row(mtx_matrix_t mtx, int32 row,
351 const mtx_range_t *colrng);
352 /**<
353 *** Compute sum of squares of non-zeros in the given row whose column index
354 *** lies in the given column range.
355 ***
356 -$- Returns 0.0 from a bad matrix.
357 **/
358 extern real64 mtx_sum_sqrs_in_col(mtx_matrix_t mtx, int32 col,
359 const mtx_range_t *rowrng);
360 /**<
361 *** Compute sum of squares of non-zeros in the given column whose row index
362 *** lies in the given row range.
363 ***
364 -$- Returns 0.0 from a bad matrix.
365 **/
366 extern real64 mtx_sum_abs_in_row(mtx_matrix_t mtx, int32 row,
367 const mtx_range_t *colrng);
368 /**<
369 *** Compute sum of absolute values of non-zeros in the
370 *** given row whose column index lies in the given column range.
371 ***
372 -$- Returns 0.0 from a bad matrix.
373 **/
374 extern real64 mtx_sum_abs_in_col(mtx_matrix_t mtx, int32 col,
375 const mtx_range_t *rowrng);
376 /**<
377 *** Compute sum of absolute values of non-zeros in the
378 *** given column whose row index lies in the given row range.
379 ***
380 -$- Returns 0.0 from a bad matrix.
381 **/
382
383 extern real64 mtx_col_dot_full_org_vec(mtx_matrix_t mtx,
384 int32 col,
385 real64 *orgvec,
386 mtx_range_t *rowrng,
387 boolean transpose);
388 /**< See mtx_row_dot_full_org_vec(), switching row & column references. */
389 extern real64 mtx_row_dot_full_org_vec(mtx_matrix_t mtx,
390 int32 row,
391 real64 *orgvec,
392 mtx_range_t *colrng,
393 boolean transpose);
394 /**<
395 *** <pre>
396 *** For transpose==FALSE:
397 *** Compute the dot product of the row given with the org_col indexed
398 *** orgvec over the colrng given (colrng being the cur indexed
399 *** limits as usual.)
400 *** i.e. SUM( mtx(row,col_cur) * orgvec[mtx_col_to_org(mtx,col_cur)] )
401 *** for all inrange(col_cur).
402 ***
403 *** For transpose==TRUE:
404 *** Compute the dot product of the row given with the org_row indexed
405 *** orgvec over the colrng given (colrng being the cur indexed
406 *** limits as usual.)
407 *** i.e. SUM( mtx(row,col_cur) * orgvec[mtx_row_to_org(mtx,col_cur)] )
408 *** for all inrange(col_cur).
409 *** </pre>
410 -$- Returns 0.0 from a bad matrix.
411 **/
412
413 extern real64 mtx_col_dot_full_cur_vec(mtx_matrix_t mtx,
414 int32 col,
415 real64 *curcolvec,
416 mtx_range_t *rowrng,
417 boolean transpose);
418 /**< See mtx_row_dot_full_cur_vec(), switching row & column references. */
419 extern real64 mtx_row_dot_full_cur_vec(mtx_matrix_t mtx,
420 int32 row,
421 real64 *currowvec,
422 mtx_range_t *colrng,
423 boolean transpose);
424 /**<
425 *** Compute the dot product of the row given with the cur col indexed
426 *** currowvec over the colrng given (colrng being the cur indexed
427 *** limits as usual.)<br><br>
428 ***
429 -$- Returns 0.0 from a bad matrix.<br><br>
430 ***
431 ! ! Transpose is currently not implemented. A warning will be issued.
432 ! ! When someone finds a use and can explain what the transpose versions
433 ! ! of these functions do in terms of permutations, it will be coded.<br><br>
434 ***
435 *** Note: This pair of operators is slightly less expensive than
436 *** the mtx_*_dot_full_org_vec is.
437 **/
438
439 extern real64 mtx_col_dot_full_org_custom_vec(mtx_matrix_t matrix1,
440 mtx_matrix_t matrix2,
441 int32 row,
442 real64 *orgvec,
443 mtx_range_t *colrng,
444 boolean transpose);
445 /**< See mtx_row_dot_full_org_custom_vec(), switching row & column references. */
446 extern real64 mtx_row_dot_full_org_custom_vec(mtx_matrix_t matrix1,
447 mtx_matrix_t matrix2,
448 int32 col,
449 real64 *orgvec,
450 mtx_range_t *rowrng,
451 boolean transpose);
452 /**<
453 *** <pre>
454 *** For transpose==FALSE:
455 *** Compute the dot product of the row given with the org_col indexed
456 *** orgvec (wrt matrix2) over the colrng given (colrng being the cur
457 *** indexed limits of matrix1.)
458 *** i.e. SUM( mtx(row,col_cur) *
459 *** orgvec[mtx_col_to_org(mtx2,col_cur)] )
460 *** for all inrange(col_cur).
461 ***
462 *** For transpose==TRUE:
463 *** Compute the dot product of the row given with the org_row indexed
464 *** orgvec (wrt matrix2) over the colrng given (colrng being the cur
465 *** indexed limits of matrix1.)
466 *** i.e. SUM( mtx(row,col_cur) *
467 *** orgvec[mtx_row_to_org(mtx2,col_cur)] )
468 *** for all inrange(col_cur).
469 *** </pre>
470 -$- Returns 0.0 from a bad matrix.
471 **/
472
473 extern void mtx_org_vec_add_col(mtx_matrix_t mtx,
474 real64 *tvec,
475 int32 scol,
476 real64 factor,
477 mtx_range_t *rowrng,
478 boolean transpose);
479 /**< See mtx_cur_vec_add_row(), switching row & column references. */
480 extern void mtx_org_vec_add_row(mtx_matrix_t mtx,
481 real64 *tvec,
482 int32 srow,
483 real64 factor,
484 mtx_range_t *colrng,
485 boolean transpose);
486 /**< See mtx_cur_vec_add_row(). */
487 extern void mtx_cur_vec_add_col(mtx_matrix_t mtx,
488 real64 *tvec,
489 int32 scol,
490 real64 factor,
491 mtx_range_t *rowrng,
492 boolean transpose);
493 /**< See mtx_cur_vec_add_row(), switching row & column references. */
494 extern void mtx_cur_vec_add_row(mtx_matrix_t mtx,
495 real64 *tvec,
496 int32 srow,
497 real64 factor,
498 mtx_range_t *colrng,
499 boolean transpose);
500 /**<
501 *** Adds multiple factor of srow to tvec for those columns in colrng.
502 *** tvec is org/cur col indexed if transpose==FALSE.
503 *** i.e. this is just adding rows.
504 *** tvec is org/cur row indexed if transpose==TRUE.
505 *** orgvec[mtx_row_to_org(col)]+=factor*element(srow,col)
506 ! ! curvec[???]+=factor*element(srow,col)
507 ***
508 *** Since switching row and column is hard for the transpose, here it is:
509 *** orgvec[mtx_col_to_org(row)]+=factor*element(row,scol)
510 ! ! curvec[???]+=factor*element(row,scol)
511 *** <br><br>
512 *** Notes: It is faster to use this with mtx_ALL_COLS/ROWS where
513 *** possible.
514 *** Use transpose==TRUE here if you would use transpose==TRUE
515 *** for dotting the row/col with the same vector.<br><br>
516 ! ! Warning:
517 ! ! Like mtx_row/col_dot_full_cur_vec,
518 ! ! the transpose==TRUE flavors of mtx_cur_vec_add_row/col
519 ! ! are NOT implemented. Nobody has found a use for them and nobody
520 ! ! has yet cooked up what they mean in permutation terms.<br><br>
521 ***
522 -$- Does nothing to a bad matrix.
523 **/
524
525 /** @} */
526
527 #endif /* __MTX_QUERY_H_SEEN__ */

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