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