Parent Directory | 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)

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 |