1 /* ========================================================================== */ 2 /* === umf_internal.h ======================================================= */ 3 /* ========================================================================== */ 4 5 /* -------------------------------------------------------------------------- */ 6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */ 7 /* All Rights Reserved. See ../Doc/License.txt for License. */ 8 /* -------------------------------------------------------------------------- */ 9 10 /* 11 This file is for internal use in UMFPACK itself, and should not be included 12 in user code. Use umfpack.h instead. User-accessible file names and 13 routine names all start with the letters "umfpack_". Non-user-accessible 14 file names and routine names all start with "umf_". 15 */ 16 17 #ifndef _UMF_INTERNAL 18 #define _UMF_INTERNAL 19 20 /* -------------------------------------------------------------------------- */ 21 /* ANSI standard include files */ 22 /* -------------------------------------------------------------------------- */ 23 24 /* from float.h: DBL_EPSILON */ 25 #include <float.h> 26 27 /* from string.h: strcmp */ 28 #include <string.h> 29 30 /* when debugging, assert.h and the assert macro are used (see umf_dump.h) */ 31 32 /* -------------------------------------------------------------------------- */ 33 /* Architecture */ 34 /* -------------------------------------------------------------------------- */ 35 36 #if defined (__sun) || defined (MSOL2) || defined (ARCH_SOL2) 37 #define UMF_SOL2 38 #define UMFPACK_ARCHITECTURE "Sun Solaris" 39 40 #elif defined (__sgi) || defined (MSGI) || defined (ARCH_SGI) 41 #define UMF_SGI 42 #define UMFPACK_ARCHITECTURE "SGI Irix" 43 44 #elif defined (__linux) || defined (MGLNX86) || defined (ARCH_GLNX86) 45 #define UMF_LINUX 46 #define UMFPACK_ARCHITECTURE "Linux" 47 48 #elif defined (__APPLE__) 49 #define UMF_MAC 50 #define UMFPACK_ARCHITECTURE "Mac" 51 52 #elif defined (_AIX) || defined (MIBM_RS) || defined (ARCH_IBM_RS) 53 #define UMF_AIX 54 #define UMFPACK_ARCHITECTURE "IBM AIX" 55 56 #elif defined (__alpha) || defined (MALPHA) || defined (ARCH_ALPHA) 57 #define UMF_ALPHA 58 #define UMFPACK_ARCHITECTURE "Compaq Alpha" 59 60 #elif defined (_WIN32) || defined (WIN32) 61 #if defined (__MINGW32__) 62 #define UMF_MINGW 63 #elif defined (__CYGWIN32__) 64 #define UMF_CYGWIN 65 #else 66 #define UMF_WINDOWS 67 #endif 68 #define UMFPACK_ARCHITECTURE "Microsoft Windows" 69 70 #elif defined (__hppa) || defined (__hpux) || defined (MHPUX) || defined (ARCH_HPUX) 71 #define UMF_HP 72 #define UMFPACK_ARCHITECTURE "HP Unix" 73 74 #elif defined (__hp700) || defined (MHP700) || defined (ARCH_HP700) 75 #define UMF_HP 76 #define UMFPACK_ARCHITECTURE "HP 700 Unix" 77 78 #else 79 /* If the architecture is unknown, and you call the BLAS, you may need to */ 80 /* define BLAS_BY_VALUE, BLAS_NO_UNDERSCORE, and/or BLAS_CHAR_ARG yourself. */ 81 #define UMFPACK_ARCHITECTURE "unknown" 82 #endif 83 84 85 /* -------------------------------------------------------------------------- */ 86 /* basic definitions (see also amd_internal.h) */ 87 /* -------------------------------------------------------------------------- */ 88 89 #define ONES_COMPLEMENT(r) (-(r)-1) 90 91 /* -------------------------------------------------------------------------- */ 92 /* AMD include file */ 93 /* -------------------------------------------------------------------------- */ 94 95 /* stdio.h, stdlib.h, limits.h, and math.h, NDEBUG definition, assert.h */ 96 #include "amd_internal.h" 97 98 /* -------------------------------------------------------------------------- */ 99 /* MATLAB include files */ 100 /* -------------------------------------------------------------------------- */ 101 102 /* only used when compiling the UMFPACK mexFunction */ 103 #ifdef MATLAB_MEX_FILE 104 #include "matrix.h" 105 #include "mex.h" 106 #endif 107 108 /* -------------------------------------------------------------------------- */ 109 /* Real/complex and int/SuiteSparse_long definitions, double relops */ 110 /* -------------------------------------------------------------------------- */ 111 112 #include "umf_version.h" 113 114 /* -------------------------------------------------------------------------- */ 115 /* Compile-time configurations */ 116 /* -------------------------------------------------------------------------- */ 117 118 #include "umf_config.h" 119 120 /* -------------------------------------------------------------------------- */ 121 /* umfpack include file */ 122 /* -------------------------------------------------------------------------- */ 123 124 #include "umfpack.h" 125 126 /* -------------------------------------------------------------------------- */ 127 /* for contents of Info. This must correlate with umfpack.h */ 128 /* -------------------------------------------------------------------------- */ 129 130 #define ESTIMATE (UMFPACK_NUMERIC_SIZE_ESTIMATE - UMFPACK_NUMERIC_SIZE) 131 #define ACTUAL 0 132 133 /* -------------------------------------------------------------------------- */ 134 /* get a parameter from the Control array */ 135 /* -------------------------------------------------------------------------- */ 136 137 #define GET_CONTROL(i,default) \ 138 ((Control != (double *) NULL) ? \ 139 (SCALAR_IS_NAN (Control [i]) ? default : Control [i]) \ 140 : default) 141 142 /* -------------------------------------------------------------------------- */ 143 /* for clearing the external degree counters */ 144 /* -------------------------------------------------------------------------- */ 145 146 #define MAX_MARK(n) Int_MAX - (2*(n)+1) 147 148 /* -------------------------------------------------------------------------- */ 149 /* convert number of Units to MBytes */ 150 /* -------------------------------------------------------------------------- */ 151 152 #define MBYTES(units) (((units) * sizeof (Unit)) / 1048576.0) 153 154 /* -------------------------------------------------------------------------- */ 155 /* dense row/column macro */ 156 /* -------------------------------------------------------------------------- */ 157 158 /* In order for a row or column to be treated as "dense", it must have more */ 159 /* entries than the value returned by this macro. n is the dimension of the */ 160 /* matrix, and alpha is the dense row/column control parameter. */ 161 162 /* Note: this is not defined if alpha is NaN or Inf: */ 163 #define UMFPACK_DENSE_DEGREE_THRESHOLD(alpha,n) \ 164 ((Int) MAX (16.0, (alpha) * 16.0 * sqrt ((double) (n)))) 165 166 /* -------------------------------------------------------------------------- */ 167 /* PRINTF */ 168 /* -------------------------------------------------------------------------- */ 169 170 #define PRINTFk(k,params) { if (prl >= (k)) { PRINTF (params) ; } } 171 #define PRINTF1(params) PRINTFk (1, params) 172 #define PRINTF2(params) PRINTFk (2, params) 173 #define PRINTF3(params) PRINTFk (3, params) 174 #define PRINTF4(params) PRINTFk (4, params) 175 #define PRINTF5(params) PRINTFk (5, params) 176 #define PRINTF6(params) PRINTFk (6, params) 177 178 /* -------------------------------------------------------------------------- */ 179 /* Fixed control parameters */ 180 /* -------------------------------------------------------------------------- */ 181 182 /* maximum number of columns to consider at one time, in a single front */ 183 #define MAX_CANDIDATES 128 184 185 /* reduce Numeric->Memory request by this ratio, if allocation fails */ 186 #define UMF_REALLOC_REDUCTION (0.95) 187 188 /* increase Numeric->Memory request by this ratio, if we need more */ 189 #define UMF_REALLOC_INCREASE (1.2) 190 191 /* increase the dimensions of the current frontal matrix by this factor 192 * when it needs to grow. */ 193 #define UMF_FRONTAL_GROWTH (1.2) 194 195 /* largest BLAS block size permitted */ 196 #define MAXNB 64 197 198 /* if abs (y) < RECIPROCAL_TOLERANCE, then compute x/y. Otherwise x*(1/y). 199 * Ignored if NRECIPROCAL is defined */ 200 #define RECIPROCAL_TOLERANCE 1e-12 201 202 /* -------------------------------------------------------------------------- */ 203 /* Memory allocator */ 204 /* -------------------------------------------------------------------------- */ 205 206 /* see SuiteSparse_config */ 207 208 /* -------------------------------------------------------------------------- */ 209 /* Memory space definitions */ 210 /* -------------------------------------------------------------------------- */ 211 212 /* for memory alignment - assume double has worst case alignment */ 213 typedef double Align ; 214 215 /* get number of bytes required to hold n items of a type: */ 216 /* note that this will not overflow, because sizeof (type) is always */ 217 /* greater than or equal to sizeof (Int) >= 2 */ 218 #define BYTES(type,n) (sizeof (type) * (n)) 219 220 /* ceiling of (b/u). Assumes b >= 0 and u > 0 */ 221 #define CEILING(b,u) (((b) + (u) - 1) / (u)) 222 223 /* get number of Units required to hold n items of a type: */ 224 #define UNITS(type,n) (CEILING (BYTES (type, n), sizeof (Unit))) 225 226 /* same as DUNITS, but use double instead of int to avoid overflow */ 227 #define DUNITS(type,n) (ceil (BYTES (type, (double) n) / sizeof (Unit))) 228 229 union Unit_union 230 { /* memory is allocated in multiples of Unit */ 231 struct 232 { 233 Int 234 size, /* size, in Units, of the block, excl. header block */ 235 /* size >= 0: block is in use */ 236 /* size < 0: block is free, of |size| Units */ 237 prevsize ; /* size, in Units, of preceding block in S->Memory */ 238 /* during garbage_collection, prevsize is set to -e-1 */ 239 /* for element e, or positive (and thus a free block) */ 240 /* otherwise */ 241 } header ; /* block header */ 242 Align xxxxxx ; /* force alignment of blocks (xxxxxx is never used) */ 243 } ; 244 245 typedef union Unit_union Unit ; 246 247 /* get the size of an allocated block */ 248 #define GET_BLOCK_SIZE(p) (((p)-1)->header.size) 249 250 /* -------------------------------------------------------------------------- */ 251 /* Numeric */ 252 /* -------------------------------------------------------------------------- */ 253 254 /* 255 NUMERIC_VALID and SYMBOLIC_VALID: 256 The different values of SYBOLIC_VALID and NUMERIC_VALID are chosen as a 257 first defense against corrupted *Symbolic or *Numeric pointers passed to an 258 UMFPACK routine. They also ensure that the objects are used only by the 259 same version that created them (umfpack_di_*, umfpack_dl_*, umfpack_zi_*, 260 or umfpack_zl_*). The values have also been changed since prior releases of 261 the code to ensure that all routines that operate on the objects are of the 262 same release. The values themselves are purely arbitrary. The are less 263 than the ANSI C required minimums of INT_MAX and LONG_MAX, respectively. 264 */ 265 266 #ifdef DINT 267 #define NUMERIC_VALID 15977 268 #define SYMBOLIC_VALID 41937 269 #endif 270 #ifdef DLONG 271 #define NUMERIC_VALID 399789720 272 #define SYMBOLIC_VALID 399192713 273 #endif 274 #ifdef ZINT 275 #define NUMERIC_VALID 17957 276 #define SYMBOLIC_VALID 40927 277 #endif 278 #ifdef ZLONG 279 #define NUMERIC_VALID 129987754 280 #define SYMBOLIC_VALID 110291734 281 #endif 282 283 typedef struct /* NumericType */ 284 { 285 double 286 flops, /* "true" flop count */ 287 relpt, /* relative pivot tolerance used */ 288 relpt2, /* relative pivot tolerance used for sym. */ 289 droptol, 290 alloc_init, /* initial allocation of Numeric->memory */ 291 front_alloc_init, /* frontal matrix allocation parameter */ 292 rsmin, /* smallest row sum */ 293 rsmax, /* largest row sum */ 294 min_udiag, /* smallest abs value on diagonal of D */ 295 max_udiag, /* smallest abs value on diagonal of D */ 296 rcond ; /* min (D) / max (D) */ 297 298 Int 299 scale ; 300 301 Int valid ; /* set to NUMERIC_VALID, for validity check */ 302 303 /* Memory space for A and LU factors */ 304 Unit 305 *Memory ; /* working memory for A and LU factors */ 306 Int 307 ihead, /* pointer to tail of LU factors, in Numeric->Memory */ 308 itail, /* pointer to top of elements & tuples, */ 309 /* in Numeric->Memory */ 310 ibig, /* pointer to largest free block seen in tail */ 311 size ; /* size of Memory, in Units */ 312 313 Int 314 *Rperm, /* pointer to row perm array, size: n+1 */ 315 /* after UMF_kernel: Rperm [new] = old */ 316 /* during UMF_kernel: Rperm [old] = new */ 317 *Cperm, /* pointer to col perm array, size: n+1 */ 318 /* after UMF_kernel: Cperm [new] = old */ 319 /* during UMF_kernel: Cperm [old] = new */ 320 321 *Upos, /* see UMFPACK_get_numeric for a description */ 322 *Lpos, 323 *Lip, 324 *Lilen, 325 *Uip, 326 *Uilen, 327 *Upattern ; /* pattern of last row of U (if singular) */ 328 329 Int 330 ulen, /* length of Upattern */ 331 npiv, /* number of structural pivots found (sprank approx) */ 332 nnzpiv ; /* number of numerical (nonzero) pivots found */ 333 334 Entry 335 *D ; /* D [i] is the diagonal entry of U */ 336 337 Int do_recip ; 338 double *Rs ; /* scale factors for the rows of A and b */ 339 /* do_recip FALSE: Divide row i by Rs [i] */ 340 /* do_recip TRUE: Multiply row i by Rs [i] */ 341 342 Int 343 n_row, n_col, /* A is n_row-by-n_row */ 344 n1 ; /* number of singletons */ 345 346 /* for information only: */ 347 Int 348 tail_usage, /* amount of memory allocated in tail */ 349 /* head_usage is Numeric->ihead */ 350 init_usage, /* memory usage just after UMF_kernel_init */ 351 max_usage, /* peak memory usage (excludes internal and external */ 352 /* fragmentation in the tail) */ 353 ngarbage, /* number of garbage collections performed */ 354 nrealloc, /* number of reallocations performed */ 355 ncostly, /* number of costly reallocations performed */ 356 isize, /* size of integer pattern of L and U */ 357 nLentries, /* number of entries in L, excluding diagonal */ 358 nUentries, /* number of entries in U, including diagonal */ 359 /* Some entries may be numerically zero. */ 360 lnz, /* number of nonzero entries in L, excl. diagonal */ 361 all_lnz, /* lnz plus entries dropped from L */ 362 unz, /* number of nonzero entries in U, excl. diagonal */ 363 all_unz, /* unz plus entries dropped form U */ 364 maxfrsize ; /* largest actual front size */ 365 366 Int maxnrows, maxncols ; /* not the same as Symbolic->maxnrows/cols* */ 367 368 } NumericType ; 369 370 371 372 /* -------------------------------------------------------------------------- */ 373 /* Element tuples for connecting elements together in a matrix */ 374 /* -------------------------------------------------------------------------- */ 375 376 typedef struct /* Tuple */ 377 { 378 /* The (e,f) tuples for the element lists */ 379 Int 380 e, /* element */ 381 f ; /* contribution to the row/col appears at this offset */ 382 383 } Tuple ; 384 385 #define TUPLES(t) MAX (4, (t) + 1) 386 387 /* Col_degree is aliased with Cperm, and Row_degree with Rperm */ 388 #define NON_PIVOTAL_COL(col) (Col_degree [col] >= 0) 389 #define NON_PIVOTAL_ROW(row) (Row_degree [row] >= 0) 390 391 /* -------------------------------------------------------------------------- */ 392 /* An element */ 393 /* -------------------------------------------------------------------------- */ 394 395 typedef struct /* Element */ 396 { 397 Int 398 399 cdeg, /* external column degree + cdeg0 offset */ 400 rdeg, /* external row degree + rdeg0 offset */ 401 nrowsleft, /* number of rows remaining */ 402 ncolsleft, /* number of columns remaining */ 403 nrows, /* number of rows */ 404 ncols, /* number of columns */ 405 next ; /* for list link of sons, used during assembly only */ 406 407 /* followed in memory by: 408 Int 409 col [0..ncols-1], column indices of this element 410 row [0..nrows-1] ; row indices of this element 411 Entry (suitably aligned, see macro below) 412 C [0...nrows-1, 0...ncols-1] ; 413 size of C is nrows*ncols Entry's 414 */ 415 416 } Element ; 417 418 /* macros for computing pointers to row/col indices, and contribution block: */ 419 420 #define GET_ELEMENT_SIZE(nr,nc) \ 421 (UNITS (Element, 1) + UNITS (Int, (nc) + (nr)) + UNITS (Entry, (nc) * (nr))) 422 423 #define DGET_ELEMENT_SIZE(nr,nc) \ 424 (DUNITS (Element, 1) + DUNITS (Int, (nc) + (nr)) + DUNITS (Entry, (nc) * (nr))) 425 426 #define GET_ELEMENT_COLS(ep,p,Cols) { \ 427 ASSERT (p != (Unit *) NULL) ; \ 428 ASSERT (p >= Numeric->Memory + Numeric->itail) ; \ 429 ASSERT (p <= Numeric->Memory + Numeric->size) ; \ 430 ep = (Element *) p ; \ 431 p += UNITS (Element, 1) ; \ 432 Cols = (Int *) p ; \ 433 } 434 435 #define GET_ELEMENT_PATTERN(ep,p,Cols,Rows,ncm) { \ 436 GET_ELEMENT_COLS (ep, p, Cols) ; \ 437 ncm = ep->ncols ; \ 438 Rows = Cols + ncm ; \ 439 } 440 441 #define GET_ELEMENT(ep,p,Cols,Rows,ncm,nrm,C) { \ 442 GET_ELEMENT_PATTERN (ep, p, Cols, Rows, ncm) ; \ 443 nrm = ep->nrows ; \ 444 p += UNITS (Int, ncm + nrm) ; \ 445 C = (Entry *) p ; \ 446 } 447 448 /* -------------------------------------------------------------------------- */ 449 /* Work data structure */ 450 /* -------------------------------------------------------------------------- */ 451 452 /* 453 This data structure holds items needed only during factorization. 454 All of this is freed when UMFPACK_numeric completes. Note that some of 455 it is stored in the tail end of Numeric->S (namely, the Tuples and the 456 Elements). 457 */ 458 459 typedef struct /* WorkType */ 460 { 461 462 /* ---------------------------------------------------------------------- */ 463 /* information about each row and col of A */ 464 /* ---------------------------------------------------------------------- */ 465 466 /* 467 Row_tuples: pointer to tuple list (alias with Numeric->Uip) 468 Row_tlen: number of tuples (alias with Numeric->Uilen) 469 Col_tuples: pointer to tuple list (alias with Numeric->Lip) 470 Col_tlen: number of tuples (alias with Numeric->Lilen) 471 Row_degree: degree of the row or column (alias Numeric->Rperm) 472 Col_degree: degree of the row or column (alias Numeric->Cperm) 473 474 The Row_degree and Col_degree are MATLAB-style colmmd approximations, 475 are equal to the sum of the sizes of the elements (contribution blocks) 476 in each row and column. They are maintained when elements are created 477 and assembled. They are used only during the pivot row and column 478 search. They are not needed to represent the pattern of the remaining 479 matrix. 480 */ 481 482 /* ---------------------------------------------------------------------- */ 483 /* information about each element */ 484 /* ---------------------------------------------------------------------- */ 485 486 Int *E ; /* E [0 .. Work->elen-1] element "pointers" */ 487 /* (offsets in Numeric->Memory) */ 488 489 /* ---------------------------------------------------------------------- */ 490 /* generic workspace */ 491 /* ---------------------------------------------------------------------- */ 492 493 Entry *Wx, *Wy ; /* each of size maxnrows+1 */ 494 495 Int /* Sizes: nn = MAX (n_row, n_col) */ 496 *Wp, /* nn+1 */ 497 *Wrp, /* n_col+1 */ 498 *Wm, /* maxnrows+1 */ 499 *Wio, /* maxncols+1 */ 500 *Woi, /* maxncols+1 */ 501 *Woo, /* MAX (maxnrows,maxncols)+1 */ 502 *Wrow, /* pointer to Fcols, Wio, or Woi */ 503 *NewRows, /* list of rows to scan */ 504 *NewCols ; /* list of cols to scan */ 505 506 /* ---------------------------------------------------------------------- */ 507 508 Int 509 *Lpattern, /* pattern of column of L, for one Lchain */ 510 *Upattern, /* pattern of row of U, for one Uchain */ 511 ulen, llen ; /* length of Upattern and Lpattern */ 512 513 Int 514 *Diagonal_map, /* used for symmetric pivoting, of size nn+1 */ 515 *Diagonal_imap ;/* used for symmetric pivoting, of size nn+1 */ 516 517 /* ---------------------------------------------------------------------- */ 518 519 Int 520 n_row, n_col, /* matrix is n_row-by-n_col */ 521 nz, /* nonzeros in the elements for this matrix */ 522 n1, /* number of row and col singletons */ 523 elen, /* max possible number of elements */ 524 npiv, /* number of pivot rows and columns so far */ 525 ndiscard, /* number of discarded pivot columns */ 526 Wrpflag, 527 nel, /* elements in use are in the range 1..nel */ 528 noff_diagonal, 529 prior_element, 530 rdeg0, cdeg0, 531 rrdeg, ccdeg, 532 Candidates [MAX_CANDIDATES], /* current candidate pivot columns */ 533 nCandidates, /* number of candidates in Candidate set */ 534 ksuper, 535 firstsuper, 536 jsuper, 537 ncand, /* number of candidates (some not in Candidates[ ]) */ 538 nextcand, /* next candidate to place in Candidate search set */ 539 lo, 540 hi, 541 pivrow, /* current pivot row */ 542 pivcol, /* current pivot column */ 543 do_extend, /* true if the next pivot extends the current front */ 544 do_update, /* true if update should be applied */ 545 nforced, /* number of forced updates because of frontal growth */ 546 any_skip, 547 do_scan2row, 548 do_scan2col, 549 do_grow, 550 pivot_case, 551 frontid, /* id of current frontal matrix */ 552 nfr ; /* number of frontal matrices */ 553 554 /* ---------------------------------------------------------------------- */ 555 /* For row-merge tree */ 556 /* ---------------------------------------------------------------------- */ 557 558 Int 559 *Front_new1strow ; 560 561 /* ---------------------------------------------------------------------- */ 562 /* current frontal matrix, F */ 563 /* ---------------------------------------------------------------------- */ 564 565 Int Pivrow [MAXNB], 566 Pivcol [MAXNB] ; 567 568 Entry 569 *Flublock, /* LU block, nb-by-nb */ 570 *Flblock, /* L block, fnr_curr-by-nb */ 571 *Fublock, /* U block, nb-by-fnc_curr, or U' fnc_curr-by-nb */ 572 *Fcblock ; /* C block, fnr_curr-by-fnc_curr */ 573 574 Int 575 *Frows, /* Frows [0.. ]: row indices of F */ 576 577 *Fcols, /* Fcols [0.. ]: column indices of F */ 578 579 *Frpos, /* position of row indices in F, or -1 if not present */ 580 /* if Frows[i] == row, then Frpos[row] == i */ 581 582 *Fcpos, /* position of col indices in F, or -1 if not present */ 583 /* if Fcols[j] == col, then */ 584 /* Fcpos[col] == j*Work->fnr_curr */ 585 586 fnrows, /* number of rows in contribution block in F */ 587 fncols, /* number of columns in contribution block in F */ 588 fnr_curr, /* maximum # of rows in F (leading dimension) */ 589 fnc_curr, /* maximum # of columns in F */ 590 fcurr_size, /* current size of F */ 591 fnrows_max, /* max possible column-dimension (max # of rows) of F */ 592 fncols_max, /* max possible row-dimension (max # of columns) of F */ 593 nb, 594 fnpiv, /* number of pivots in F */ 595 fnzeros, /* number of explicit zero entries in LU block */ 596 fscan_row, /* where to start scanning rows of F in UMF_assemble */ 597 fscan_col, /* where to start scanning cols of F in UMF_assemble */ 598 fnrows_new, /* number of new row indices in F after pivot added */ 599 fncols_new, /* number of new col indices in F after pivot added */ 600 pivrow_in_front, /* true if current pivot row in Frows */ 601 pivcol_in_front ; /* true if current pivot column in Fcols */ 602 603 /* ---------------------------------------------------------------------- 604 * Current frontal matrix 605 * ---------------------------------------------------------------------- 606 * The current frontal matrix is held as a single block of memory allocated 607 * from the "tail" end of Numeric->Memory. It is subdivided into four 608 * parts: an LU block, an L block, a U block, and a C block. 609 * 610 * Let k = fnpiv, r = fnrows, and c = fncols for the following discussion. 611 * Let dr = fnr_curr and dc = fnc_curr. Note that r <= dr and c <= dc. 612 * 613 * The LU block is of dimension nb-by-nb. The first k-by-k part holds the 614 * "diagonal" part of the LU factors for these k pivot rows and columns. 615 * The k pivot row and column indices in this part are Pivrow [0..k-1] and 616 * Pivcol [0..k-1], respectively. 617 * 618 * The L block is of dimension dr-by-nb. It holds the k pivot columns, 619 * except for the leading k-by-k part in the LU block. Only the leading 620 * r-by-k part is in use. 621 * 622 * The U block is of dimension dc-by-nb. It holds the k pivot rows, 623 * except for the leading k-by-k part in the LU block. It is stored in 624 * row-oriented form. Only the leading c-by-k part is in use. 625 * 626 * The C block is of dimension dr-by-dc. It holds the current contribution 627 * block. Only the leading r-by-c part is in use. The column indices in 628 * the C block are Fcols [0..c-1], and the row indices are Frows [0..r-1]. 629 * 630 * dr is always odd, to avoid bad cache behavior. 631 */ 632 633 } WorkType ; 634 635 636 /* -------------------------------------------------------------------------- */ 637 /* Symbolic */ 638 /* -------------------------------------------------------------------------- */ 639 640 /* 641 This is is constructed by UMFPACK_symbolic, and is needed by UMFPACK_numeric 642 to factor the matrix. 643 */ 644 645 typedef struct /* SymbolicType */ 646 { 647 648 double 649 num_mem_usage_est, /* estimated max Numeric->Memory size */ 650 num_mem_size_est, /* estimated final Numeric->Memory size */ 651 peak_sym_usage, /* peak Symbolic and SymbolicWork usage */ 652 sym, /* symmetry of pattern */ 653 dnum_mem_init_usage, /* min Numeric->Memory for UMF_kernel_init */ 654 amd_lunz, /* nz in LU for AMD, with symmetric pivoting */ 655 lunz_bound ; /* max nx in LU, for arbitrary row pivoting */ 656 657 Int valid, /* set to SYMBOLIC_VALID, for validity check */ 658 max_nchains, 659 nchains, 660 *Chain_start, 661 *Chain_maxrows, 662 *Chain_maxcols, 663 maxnrows, /* largest number of rows in any front */ 664 maxncols, /* largest number of columns in any front */ 665 *Front_npivcol, /* Front_npivcol [j] = size of jth supercolumn*/ 666 *Front_1strow, /* first row in front j */ 667 *Front_leftmostdesc, /* leftmost desc of front j */ 668 *Front_parent, /* super-column elimination tree */ 669 *Cperm_init, /* initial column ordering */ 670 *Rperm_init, /* initial row ordering */ 671 *Cdeg, *Rdeg, 672 *Esize, 673 dense_row_threshold, 674 n1, /* number of singletons */ 675 nempty, /* MIN (nempty_row, nempty_col) */ 676 *Diagonal_map, /* initial "diagonal" */ 677 esize, /* size of Esize array */ 678 nfr, 679 n_row, n_col, /* matrix A is n_row-by-n_col */ 680 nz, /* nz of original matrix */ 681 nb, /* block size for BLAS 3 */ 682 num_mem_init_usage, /* min Numeric->Memory for UMF_kernel_init */ 683 nempty_row, nempty_col, 684 685 strategy, 686 ordering, 687 fixQ, 688 prefer_diagonal, 689 nzaat, 690 nzdiag, 691 amd_dmax ; 692 693 } SymbolicType ; 694 695 696 /* -------------------------------------------------------------------------- */ 697 /* for debugging only: */ 698 /* -------------------------------------------------------------------------- */ 699 700 #include "umf_dump.h" 701 702 /* -------------------------------------------------------------------------- */ 703 /* for statement coverage testing only: */ 704 /* -------------------------------------------------------------------------- */ 705 706 #ifdef TESTING 707 708 /* for testing integer overflow: */ 709 #ifdef TEST_FOR_INTEGER_OVERFLOW 710 #undef MAX_MARK 711 #define MAX_MARK(n) (3*(n)) 712 #endif 713 714 /* for testing out-of-memory conditions: */ 715 #define UMF_TCOV_TEST 716 717 #ifndef EXTERN 718 #define EXTERN extern 719 #endif 720 721 GLOBAL EXTERN int umf_fail, umf_fail_lo, umf_fail_hi ; 722 GLOBAL EXTERN int umf_realloc_fail, umf_realloc_lo, umf_realloc_hi ; 723 724 /* for testing malloc count: */ 725 #define UMF_MALLOC_COUNT 726 727 #endif 728 729 #endif 730