File size: 14,987 Bytes
10f2621 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 | /**
* @file mtool.h
* @ingroup global_mc
* @brief Some sparse matrix tools.
* @author Michael Holst
* @note None
* @version $Id: mtool.h,v 1.30 2010/08/12 05:18:35 fetk Exp $
*
* @attention
* @verbatim
*
* MC = < Manifold Code >
* Copyright (C) 1994-- Michael Holst
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* @endverbatim
*/
#ifndef _MTOOL_H_
#define _MTOOL_H_
#include <mc/mc_base.h>
/*
* ***************************************************************************
* Class MTOOL: Parameters and datatypes
* ***************************************************************************
*/
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef struct Link {
/** @brief the index of array */
int idx;
/** @brief Point to the next element in the list */
struct Link *next;
} Link;
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef struct LinkA {
/** @brief the index of array */
int idx;
/** @brief value of the sparse matrix component */
double val;
/** @brief Point to the next element in the list */
struct LinkA *next;
} LinkA;
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef struct LinkRC {
/** @brief the index of array */
int idx;
/** @brief Point to the next element in the list */
struct LinkRC *next;
/** @brief the index of trans array */
int idxT;
/** @brief Point to the next element in the trans list */
struct LinkRC *nextT;
} LinkRC;
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef struct LinkRCS {
/** @brief the index of array */
int idx;
/** @brief Point to the next element in the list */
struct LinkRC *next;
/** @brief the index of trans array */
int idxT;
/** @brief Point to the next element in the trans list */
struct LinkRC *nxtT;
/** @brief value of the sparse matrix component */
double val;
} LinkRCS;
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef struct LinkRCN {
/** @brief the index of array */
int idx;
/** @brief Point to the next element in the list */
struct LinkRC *next;
/** @brief the index of trans array */
int idxT;
/** @brief Point to the next element in the trans list */
struct LinkRC *nxtT;
/** @brief value of the sparse matrix component */
double val;
/** @brief value of the trans sparse matrix component */
double valT;
} LinkRCN;
/**
* @ingroup global_mc
* @brief A sparse matrix tool
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef enum MATformat {
ZERO_FORMAT,
DRC_FORMAT,
ROW_FORMAT,
COL_FORMAT,
SLU_FORMAT,
RLN_FORMAT,
CLN_FORMAT,
XLN_FORMAT,
RFL_FORMAT,
CFL_FORMAT
} MATformat;
/**
* @ingroup global_mc
* @brief matrix symmantec options
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef enum MATsym {
ISNOT_SYM,
IS_SYM,
STRUC_SYM
} MATsym;
/**
* @ingroup global_mc
* @brief matrix mirrow options
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef enum MATmirror {
ISNOT_MIRROR,
IS_MIRROR
} MATmirror;
/**
* @ingroup global_mc
* @brief the sparse matrix impl
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef enum MATimpl {
ISNOT_IMPL,
IS_IMPL
} MATimpl;
/**
* @ingroup global_mc
* @brief different states of the sparse matrix
* @author Michael Holst
* @note Class MTOOL: Parameters and datatypes
*/
typedef enum MATstate {
NULL_STATE,
ZERO_STATE,
ASSEMBLED_STATE,
FACTORED_STATE
} MATstate;
/*
* ***************************************************************************
* Class MTOOL: Inlineable methods (mtool.c)
* ***************************************************************************
*/
#if !defined(VINLINE_BAM)
#else /* if defined(VINLINE_BAM) */
#endif /* if !defined(VINLINE_BAM) */
/**
* @ingroup global_mc
* @brief Set or add a value to a matrix row/column.
* @author Michael Holst
* @note Class MTOOL: Non-inlineable methods (mtool.c)
* @return None
* @param IA pos in JA/offU/offL for row/col start
* @param JA row/col indices for nonzeros in col/row
* @param A packed nozeros:
* DRC: [ diag ; offU ; offL ]
* ROW: [ offU ]
* COL: [ offL ]
* RFL: [ everything; stored row-wise ]
* CFL: [ everything; stored col-wise ]
* @param key 0 ==> Set the value, 1 ==> Add the value
* @param i an index
* @param j an index
* @param val the value of the matrix component
*/
VEXTERNC void mPlaceit(int *IA, int *JA, double *A,
int key, int i, int j, double val);
/**
* @ingroup global_mc
* @brief Set or add a value to a linked matrix entry list.
* @author Michael Holst
* @note Class MTOOL: Non-inlineable methods (mtool.c)
* @return None
* @param mtpool Pointer to a Class Vset
* @param key 0 ==> Set the value, 1 ==> Add the value
* @param count Pointer to the inserted position
* @param i an index
* @param j an index
* @param val the value of the matrix component
*/
VEXTERNC void mContrib(Vset *mtpool,
int key, int *count, int i, int j, double val);
/**
* @ingroup global_mc
* @brief Add a link to a linked graph entry list.
* @authors Michael Holst and Stephen Bond
* @note Class MTOOL: Non-inlineable methods (mtool.c)
* @return None
* @param mtpool Pointer to a Class Vset
* @param count Pointer to the inserted position
* @param i an index
* @param j an index
*/
VEXTERNC void lContrib(Vset *mtpool, int *count, int i, int j);
/**
* @ingroup global_mc
* @brief Builds an index (and value) array in transposed format given
* the index and value array of a ROW or COL matrix.
* @author Stephen Bond
* @note Class MTOOL: Non-inlineable methods (mtool.c)\n
* (flag == 0) Build index array only, don't use matrix values.\n
* (flag == 1) Build index array only, guard against zero values.\n
* (flag == 2) Build index and val array, don't guard for zeros.\n
* (flag == 3) Build index and val arrays, guard for zero values.\n\n
* If the original A is ROW (COL) it must be of size nxm (mxn).\n
* Hence, IJA, A, and work are n+1+numO, numO, and m respectively.
* @return None
* @param vmem Memory management object
* @param IJAT Pointer to the index array
* @param AT Pointer to the trasposed A array
* @param ATnumO number of nonzeros in each row (col)
* @param IJA integer structure [ IA ; JA ]
* @param A packed nozeros:
* DRC: [ diag ; offU ; offL ]
* ROW: [ offU ]
* COL: [ offL ]
* RFL: [ everything; stored row-wise ]
* CFL: [ everything; stored col-wise ]
* @param n an index
* @param m an index
* @param flag 0 ==> Build index array only, don't use matrix values.\n
* 1 ==> Build index array only, guard against zero values.\n
* 2 ==> Build index and val array, don't guard for zeros.\n
* 3 ==> Build index and val arrays, guard for zero values.
* @param work Pointer to the work array with zeros
*/
VEXTERNC void mBuildGraphT(Vmem *vmem, int **IJAT, double **AT, int *ATnumO,
int *IJA, double *A, int n, int m, int flag, int *work);
/**
* @ingroup global_mc
* @brief Produce the sparse triple matrix product: B = R*A*P,
* where A is a sparse NxN square matrix, R is a sparse
* MxN retangular matrix, and P is a sparse NxM rectangular
* matrix, with M < N (possibly M << N).\n
* The result is a smaller (but possibly much more dense)
* square MxM matrix B.
* @author Michael Holst
* @note Class MTOOL: Non-inlineable methods (mtool.c)\n
* @verbatim
* The input matrices R,A,P are assumed to have the following
* storage formats: R is stored column-wise (ROW-format), P is
* stored row-wise (ROW-format), and A is stored in one of three
* forms, namely, either row-wise (ROW), col-wise (COL), or by
* diagonal followed by upper-triangle row-wise and then by lower
* triangle columne-wise (DRC). The resulting B is stored in the
* same format as the input matrix A. I.e., the matrices have the
* following possible storage format combinations:
*
* The matrices A and B in DRC format:
*
* B = R * A * P
*
* \-- | | | | | | | \------ ---
* |\- = | | | | | | | * |\----- * ---
* ||\ | | | | | | | ||\---- ---
* |||\--- ---
* ||||\-- ---
* |||||\- ---
* ||||||\ ---
*
* Or, the matrices A and B in ROW format:
*
* B = R * A * P
*
* --- | | | | | | | ------- ---
* --- = | | | | | | | * ------- * ---
* --- | | | | | | | ------- ---
* ------- ---
* ------- ---
* ------- ---
* ------- ---
*
* Or, finally, the matrices A and B in COL format:
*
* B = R * A * P
*
* ||| | | | | | | | ||||||| ---
* ||| = | | | | | | | * ||||||| * ---
* ||| | | | | | | | ||||||| ---
* ||||||| ---
* ||||||| ---
* ||||||| ---
* ||||||| ---
*
* We compute the product B = R*A*P by splitting up A into its
* three structures A=D+L+U, and then by splitting up the sum:
*
* B = R*D*P + R*L*P + R*U*P
*
* In the case of A in ROW form, only the last term is
* present. In the case of COL form, only the middle
* term is present. In the DRC case, all terms are present.
* Note that in the ROW and COL forms, U and L are not
* actually upper and lower triangular, but general rectangular
* matrices; this is all that we need here. In the DRC form,
* they are strict triangles, but we never use this fact directly.
*
* The first and last terms are easy to compute using the
* datastructures used for R,D,U,P. However, the middle term
* R*L*P is not straightforward to compute directly, since the
* lower-triangle L of A is stored column-wise rather than
* row-wise. However, this product can be easily formed by
* computing its transpose instead:
*
* B = R*D*P + (P^T*L^T*R^T)^T + R*U*P
*
* The product P^T*L^T*R^T is easy to compute using the column-wise
* structure of L, hence row-wise structure of L^T; the result is
* then transposed and added into B.
*
* The product is formed component-wise; no temporary matrices
* are stored, except for a linked-list structure to build the
* non-zero structure of B, which is not possible to predict
* without actually doing the product (at least symbolically).
* @endverbatim
* @return None
* @param vmem Memory management object
* @param frmt possible format types of this matrix
* @param sym symmetry keys for the matrix
* @param m an index
* @param n an index
* @param numO num of nonzeros we are actually storing in the strict upper-triangle of
* matrix. (DRC only)
* @param numA num of nonzeros we are actually storing, counting the diagonal, the strict
* upper-triangle, and also the strict lower-triangle if we are actually
* storing the lower-triangle (sym=0).
* @param ijb Pointer to memory location of the arry ijb
* @param b Pointer to memory location of the arry b
* @param ib Pointer to memory location of the arry ib
* @param jb Pointer to memory location of the arry jb
* @param diagb Pointer to memory location of the arry diagb
* @param offUb Pointer to memory location of the arry offUb
* @param offLb Pointer to memory location of the arry offLb
* @param ir Pointer to the arry ir
* @param jr Pointer to the arry jr
* @param r Pointer to the arry r
* @param ia Pointer to the arry ia
* @param ja Pointer to the arry ja
* @param a Pointer to the arry a
* @param diag Pointer to the arry diag
* @param offU Pointer to the arry offU
* @param offL Pointer to the arry offL
* @param ip Pointer to the arry ip
* @param jp Pointer to the arry jp
* @param p Pointer to the arry p
*/
VEXTERNC void buildG(Vmem *vmem, MATformat frmt, MATsym sym,
int m, int n, int *numO, int *numA,
int **ijb, double **b,
int **ib, int **jb, double **diagb, double **offUb, double **offLb,
int *ir, int *jr, double *r,
int *ia, int *ja, double *a,
double *diag, double *offU, double *offL,
int *ip, int *jp, double *p);
#endif /* _MTOOL_H_ */
|