1 /* ETree.h */ 2 3 #include "../SPOOLES.h" 4 #include "../cfiles.h" 5 #include "../Graph.h" 6 #include "../Tree.h" 7 #include "../IV.h" 8 #include "../DV.h" 9 10 /*--------------------------------------------------------------------*/ 11 /* 12 --------------------------------------------------------------------- 13 the ETree object is a tree that has a weight associated with 14 each node and a weight associated with each node's boundary. 15 it is useful to model: 16 (1) a vertex elimination tree (for a unit weight graph), 17 (2) a compressed vertex elimination tree (for a compressed graph), 18 (3) a front tree (for a factor graph) 19 20 nfront -- # of fronts 21 nvtx -- # of vertices 22 tree -- pointer to a Tree object, size nfront 23 nodwghtsIV -- IV object of node weights, size nfront 24 bnwwghtsIV -- IV object of node boundary weights, size nfront 25 vtxToFrontIV -- IV object that holds the map from vertices to fronts, 26 size nvtx 27 28 created -- 96jun23, cca 29 --------------------------------------------------------------------- 30 */ 31 typedef struct _ETree ETree ; 32 struct _ETree { 33 int nfront ; 34 int nvtx ; 35 Tree *tree ; 36 IV *nodwghtsIV ; 37 IV *bndwghtsIV ; 38 IV *vtxToFrontIV ; 39 } ; 40 /*--------------------------------------------------------------------*/ 41 /* 42 ------------------------------------------------------------------------ 43 ----- methods founds in basics.c --------------------------------------- 44 ------------------------------------------------------------------------ 45 */ 46 /* 47 ----------------------------------------------- 48 purpose -- create and return a new ETree object 49 50 created -- 95nov15, cca 51 ----------------------------------------------- 52 */ 53 ETree * 54 ETree_new ( 55 void 56 ) ; 57 /* 58 ------------------------------------------------------ 59 purpose -- set the default fields for the ETree object 60 61 created -- 95nov15, cca 62 ------------------------------------------------------ 63 */ 64 void 65 ETree_setDefaultFields ( 66 ETree *etree 67 ) ; 68 /* 69 -------------------------------- 70 purpose -- clear the data fields 71 72 created -- 95nov15, cca 73 -------------------------------- 74 */ 75 void 76 ETree_clearData ( 77 ETree *etree 78 ) ; 79 /* 80 -------------------------------- 81 purpose -- free the ETree object 82 83 created -- 95nov15, cca 84 -------------------------------- 85 */ 86 void 87 ETree_free ( 88 ETree *etree 89 ) ; 90 /*--------------------------------------------------------------------*/ 91 /* 92 ------------------------------------------------------------------------ 93 ----- methods founds in instance.c ------------------------------------- 94 ------------------------------------------------------------------------ 95 */ 96 /* 97 --------------------------- 98 return the number of fronts 99 100 created -- 97feb28, cca 101 --------------------------- 102 */ 103 int 104 ETree_nfront ( 105 ETree *etree 106 ) ; 107 /* 108 ----------------------------- 109 return the number of vertices 110 111 created -- 97feb28, cca 112 ----------------------------- 113 */ 114 int 115 ETree_nvtx ( 116 ETree *etree 117 ) ; 118 /* 119 ----------------------------------- 120 return a pointer to the Tree object 121 122 created -- 97feb28, cca 123 ----------------------------------- 124 */ 125 Tree * 126 ETree_tree ( 127 ETree *etree 128 ) ; 129 /* 130 --------------------------- 131 return the root of the tree 132 133 created -- 97feb28, cca 134 --------------------------- 135 */ 136 int 137 ETree_root ( 138 ETree *etree 139 ) ; 140 /* 141 ------------------------------------- 142 return a pointer to the parent vector 143 144 created -- 97feb28, cca 145 ------------------------------------- 146 */ 147 int * 148 ETree_par ( 149 ETree *etree 150 ) ; 151 /* 152 ------------------------------------------ 153 return a pointer to the first child vector 154 155 created -- 97feb28, cca 156 ------------------------------------------ 157 */ 158 int * 159 ETree_fch ( 160 ETree *etree 161 ) ; 162 /* 163 -------------------------------------- 164 return a pointer to the sibling vector 165 166 created -- 97feb28, cca 167 -------------------------------------- 168 */ 169 int * 170 ETree_sib ( 171 ETree *etree 172 ) ; 173 /* 174 ------------------------------------------ 175 return a pointer to the nodwghts IV object 176 177 created -- 97feb28, cca 178 ------------------------------------------ 179 */ 180 IV * 181 ETree_nodwghtsIV ( 182 ETree *etree 183 ) ; 184 /* 185 ------------------------------------------- 186 return a pointer to the nodwghts int vector 187 188 created -- 97feb28, cca 189 ------------------------------------------- 190 */ 191 int * 192 ETree_nodwghts ( 193 ETree *etree 194 ) ; 195 /* 196 ------------------------------------------ 197 return a pointer to the bndwghts IV object 198 199 created -- 97feb28, cca 200 ------------------------------------------ 201 */ 202 IV * 203 ETree_bndwghtsIV ( 204 ETree *etree 205 ) ; 206 /* 207 ------------------------------------------- 208 return a pointer to the bndwghts int vector 209 210 created -- 97feb28, cca 211 ------------------------------------------- 212 */ 213 int * 214 ETree_bndwghts ( 215 ETree *etree 216 ) ; 217 /* 218 -------------------------------------------- 219 return a pointer to the vtxToFront IV object 220 221 created -- 97feb28, cca 222 -------------------------------------------- 223 */ 224 IV * 225 ETree_vtxToFrontIV ( 226 ETree *etree 227 ) ; 228 /* 229 --------------------------------------------- 230 return a pointer to the vtxToFront int vector 231 232 created -- 97feb28, cca 233 --------------------------------------------- 234 */ 235 int * 236 ETree_vtxToFront ( 237 ETree *etree 238 ) ; 239 /* 240 ------------------------------------------------ 241 purpose -- return the number of internal degrees 242 of freedom in front J 243 244 created -- 97may23, cca 245 ------------------------------------------------ 246 */ 247 int 248 ETree_frontSize ( 249 ETree *etree, 250 int J 251 ) ; 252 /* 253 ------------------------------------------------ 254 purpose -- return the number of external degrees 255 of freedom in front J 256 257 created -- 97may23, cca 258 ------------------------------------------------ 259 */ 260 int 261 ETree_frontBoundarySize ( 262 ETree *etree, 263 int J 264 ) ; 265 /* 266 ------------------------------------------------------------ 267 purpose -- compute the maximum number of indices and entries 268 in a front 269 270 symflag = 1 --> 271 count only column indices 272 count upper entries in (1,1) block and (1,2) block 273 symflag = 2 --> 274 count row and column indices 275 count entries in (1,1), (1,2) and (2,1) blocks 276 277 created -- 97may23, cca 278 ------------------------------------------------------------ 279 */ 280 void 281 ETree_maxNindAndNent ( 282 ETree *etree, 283 int symflag, 284 int *pmaxnind, 285 int *pmaxnent 286 ) ; 287 /*--------------------------------------------------------------------*/ 288 /* 289 ------------------------------------------------------------------------ 290 ----- methods founds in util.c ----------------------------------------- 291 ------------------------------------------------------------------------ 292 */ 293 /* 294 ---------------------------------------------- 295 return the number of bytes taken by the object 296 297 created -- 95nov15, cca 298 ---------------------------------------------- 299 */ 300 int 301 ETree_sizeOf ( 302 ETree *etree 303 ) ; 304 /* 305 ---------------------------------------- 306 return the number of factor indices 307 308 created -- 95nov15, cca 309 modified -- 96jan11, cca 310 ---------------------------------------- 311 */ 312 int 313 ETree_nFactorIndices ( 314 ETree *etree 315 ) ; 316 /* 317 ------------------------------------------ 318 return the number of factor entries 319 320 symflag -- symmetry flag 321 0 (SPOOLES_SYMMETRIC) -- symmetric 322 1 (SPOOLES_HERMITIAN) -- hermitian 323 2 (SPOOLES_NONSYMMETRIC) -- nonsymmetric 324 325 created -- 98jun05, cca 326 ------------------------------------------ 327 */ 328 int 329 ETree_nFactorEntries ( 330 ETree *etree, 331 int symflag 332 ) ; 333 /* 334 ------------------------------------------ 335 return the number of factor operations 336 337 type -- type of matrix entries 338 1 (SPOOLES_REAL) -- real entries 339 2 (SPOOLES_COMPLEX) -- complex entries 340 symflag -- symmetry flag 341 0 (SPOOLES_SYMMETRIC) -- symmetric 342 1 (SPOOLES_HERMITIAN) -- hermitian 343 2 (SPOOLES_NONSYMMETRIC) -- nonsymmetric 344 345 created -- 98jun05, cca 346 ------------------------------------------ 347 */ 348 double 349 ETree_nFactorOps ( 350 ETree *etree, 351 int type, 352 int symflag 353 ) ; 354 /* 355 ---------------------------------------- 356 return the number of entries an LU front 357 358 created -- 96dec04, cca 359 ---------------------------------------- 360 */ 361 double 362 ETree_nFactorEntriesInFront ( 363 ETree *etree, 364 int symflag, 365 int J 366 ) ; 367 /* 368 ------------------------------------------------------- 369 return the number of internal LU operations for a front 370 371 created -- 96dec04, cca 372 ------------------------------------------------------- 373 */ 374 double 375 ETree_nInternalOpsInFront ( 376 ETree *etree, 377 int type, 378 int symflag, 379 int J 380 ) ; 381 /* 382 ------------------------------------------------------- 383 return the number of external LU operations for a front 384 385 created -- 96dec04, cca 386 ------------------------------------------------------- 387 */ 388 double 389 ETree_nExternalOpsInFront ( 390 ETree *etree, 391 int type, 392 int symflag, 393 int J 394 ) ; 395 /* 396 ------------------------------------ 397 return an IV object that contains 398 the number of entries for each front 399 400 created -- 98jan30, cca 401 ------------------------------------ 402 */ 403 IV * 404 ETree_factorEntriesIV ( 405 ETree *etree, 406 int symflag 407 ) ; 408 /* 409 --------------------------------------------------------- 410 return a DV object that contains the number of operations 411 for each front using a backward looking algorithm 412 413 created -- 96dec04, cca 414 --------------------------------------------------------- 415 */ 416 DV * 417 ETree_backwardOps ( 418 ETree *etree, 419 int type, 420 int symflag, 421 int *vwghts, 422 IVL *symbfacIVL 423 ) ; 424 /* 425 --------------------------------------------------------- 426 return a DV object that contains the number of operations 427 for each front using a forward-looking algorithm 428 429 created -- 96dec04, cca 430 --------------------------------------------------------- 431 */ 432 DV * 433 ETree_forwardOps ( 434 ETree *etree, 435 int type, 436 int symflag 437 ) ; 438 /* 439 --------------------------------------------------------------- 440 given an IV object that maps uncompressed vertices to vertices, 441 create and return an ETree object that is relative to the 442 uncompressed graph. 443 444 created -- 97feb13, cca 445 --------------------------------------------------------------- 446 */ 447 ETree * 448 ETree_expand ( 449 ETree *etree, 450 IV *eqmapIV 451 ) ; 452 /*--------------------------------------------------------------------*/ 453 /* 454 ------------------------------------------------------------------------ 455 ----- methods founds in init.c ----------------------------------------- 456 ------------------------------------------------------------------------ 457 */ 458 /* 459 ----------------------------------------------- 460 initialize the object given the number of nodes 461 462 created -- 95nov15, cca 463 ----------------------------------------------- 464 */ 465 void 466 ETree_init1 ( 467 ETree *etree, 468 int nfront, 469 int nvtx 470 ) ; 471 /* 472 ---------------------------------------- 473 initialize the ETree object from a graph 474 475 created -- 95nov15, cca 476 ---------------------------------------- 477 */ 478 void 479 ETree_initFromGraph ( 480 ETree *etree, 481 Graph *g 482 ) ; 483 /* 484 -------------------------------------------------------- 485 initialize the ETree object from a graph and permutation 486 487 created -- 95nov15, cca 488 -------------------------------------------------------- 489 */ 490 void 491 ETree_initFromGraphWithPerms ( 492 ETree *etree, 493 Graph *g, 494 int newToOld[], 495 int oldToNew[] 496 ) ; 497 /* 498 -------------------------------------------------------------- 499 purpose -- initialize the front tree for a dense matrix 500 501 n -- size of the matrix 502 option -- mapping option 503 1 --> have all fronts (save the last) contain the same 504 number of vertices 505 2 --> have all fronts have roughly equal numbers of entries 506 507 created -- 96aug19, cca 508 -------------------------------------------------------------- 509 */ 510 void 511 ETree_initFromDenseMatrix ( 512 ETree *etree, 513 int n, 514 int option, 515 int param 516 ) ; 517 /* 518 ------------------------------------- 519 initialize the ETree object 520 (1) read ETree object from file 521 (2) get the old-to-new permutation 522 (3) permute the ETree 523 (4) return the old-to-new permutation 524 525 created -- 97jul13, cca 526 ------------------------------------- 527 */ 528 IV * 529 ETree_initFromFile ( 530 ETree *frontETree, 531 char *inETreeFileName, 532 int msglvl, 533 FILE *msgFile 534 ) ; 535 /*--------------------------------------------------------------------*/ 536 /* 537 ------------------------------------------------------------------------ 538 ----- methods founds in ms.c ------------------------------------------- 539 ------------------------------------------------------------------------ 540 */ 541 /* 542 ------------------------------------------------ 543 returns a compidsIV IV object that maps the 544 vertices to a domain (compids[v] > 1) 545 or to the multisector (compids[v] = 0). 546 the vertices in the multisector is specified 547 by their depth of their front in the tree. 548 549 created -- 96jan04, cca 550 ------------------------------------------------ 551 */ 552 IV * 553 ETree_msByDepth ( 554 ETree *etree, 555 int depth 556 ) ; 557 /* 558 ---------------------------------------------------------------- 559 construct a multisector based on vertices found in a subtree. 560 561 created -- 96jan04, cca 562 ---------------------------------------------------------------- 563 */ 564 IV * 565 ETree_msByNvtxCutoff ( 566 ETree *etree, 567 double cutoff 568 ) ; 569 /* 570 -------------------------------------------------- 571 construct a multisector based on the number 572 of factor entries found in a subtree. 573 574 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC 575 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 576 577 created -- 96jan04, cca 578 -------------------------------------------------- 579 */ 580 IV * 581 ETree_msByNentCutoff ( 582 ETree *etree, 583 double cutoff, 584 int symflag 585 ) ; 586 /* 587 -------------------------------------------------- 588 construct a multisector based on the number 589 of factor operations found in a subtree. 590 591 type -- type of entries, 592 SPOOLES_REAL or SPOOLES_COMPLEX 593 594 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC 595 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 596 597 created -- 96jan04, cca 598 -------------------------------------------------- 599 */ 600 IV * 601 ETree_msByNopsCutoff ( 602 ETree *etree, 603 double cutoff, 604 int type, 605 int symflag 606 ) ; 607 /* 608 -------------------------------------------------------------- 609 purpose -- given a front tree and a multisector map vector, 610 fill the map vector with domain ids and the three statistics 611 arrays with domain and schur complement statistics. 612 613 frontETree -- front tree object, unchanged on output 614 msIV -- map from fronts to domains or schur complement 615 on input, ms[J] = 0 --> J is in the schur complement 616 ms[J] = 1 --> J is not in the schur complement 617 on output, ms[J] = 0 --> J is in the schur complement 618 ms[J] != 0 --> J is in domain ms[J] 619 on output 620 nvtxIV -- nvtx[ireg] = # of dof in region ireg 621 nzfIV -- nzf[ireg] = # of factor entries in region ireg 622 opsIV -- ops[ireg] = # of factor ops in region ireg 623 624 type -- type of entries, SPOOLES_REAL or SPOOLES_COMPLEX 625 626 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC 627 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 628 629 created -- 98jan30, cca 630 -------------------------------------------------------------- 631 */ 632 void 633 ETree_msStats ( 634 ETree *frontETree, 635 IV *msIV, 636 IV *nvtxIV, 637 IV *nzfIV, 638 DV *opsDV, 639 int type, 640 int symlag 641 ) ; 642 /*--------------------------------------------------------------------*/ 643 /* 644 ------------------------------------------------------------------------ 645 ----- methods founds in permute.c -------------------------------------- 646 ------------------------------------------------------------------------ 647 */ 648 /* 649 ----------------------------------------------------- 650 fill the new-to-old permutation vector for the fronts 651 652 created -- 96jun23, cca 653 ----------------------------------------------------- 654 */ 655 IV * 656 ETree_newToOldFrontPerm ( 657 ETree *etree 658 ) ; 659 /* 660 ----------------------------------------------------- 661 fill the old-to-new permutation vector for the fronts 662 663 created -- 96jun23, cca 664 ----------------------------------------------------- 665 */ 666 IV * 667 ETree_oldToNewFrontPerm ( 668 ETree *etree 669 ) ; 670 /* 671 ------------------------------------------------------- 672 fill the new-to-old permutation vector for the vertices 673 674 created -- 96jun23, cca 675 ------------------------------------------------------- 676 */ 677 IV * 678 ETree_newToOldVtxPerm ( 679 ETree *etree 680 ) ; 681 /* 682 ------------------------------------------------------- 683 fill the old-to-new permutation vector for the vertices 684 685 created -- 96jun23, cca 686 ------------------------------------------------------- 687 */ 688 IV * 689 ETree_oldToNewVtxPerm ( 690 ETree *etree 691 ) ; 692 /* 693 ------------------------------------------------------- 694 purpose -- permute the vertices, 695 overwrite entries in the vertex-to-front map 696 697 created -- 96oct03, cca 698 ------------------------------------------------------- 699 */ 700 void 701 ETree_permuteVertices ( 702 ETree *etree, 703 IV *vtxOldToNewIV 704 ) ; 705 /*--------------------------------------------------------------------*/ 706 /* 707 ------------------------------------------------------------------------ 708 ----- methods founds in compress.c ------------------------------------- 709 ------------------------------------------------------------------------ 710 */ 711 /*--------------------------------------------------------------------*/ 712 /* 713 ------------------------------------------------------- 714 purpose -- 715 to create and return an IV object that contains the map 716 from old to new fronts that are fundamental chains. 717 718 created -- 96jun23, cca 719 ------------------------------------------------------- 720 */ 721 IV * 722 ETree_fundChainMap ( 723 ETree *etree 724 ) ; 725 /* 726 ------------------------------------------------------- 727 purpose -- 728 to create and return an IV object that contains the map 729 from old to new fronts that are fundamental supernodes. 730 731 created -- 96jun23, cca 732 ------------------------------------------------------- 733 */ 734 IV * 735 ETree_fundSupernodeMap ( 736 ETree *etree 737 ) ; 738 /* 739 ----------------------------------------------------------- 740 compress an ETree object given a map from old to new nodes. 741 note, a new node must be a connected set of the old nodes. 742 743 return value -- pointer to new ETree object 744 745 created -- 96jun23, cca. 746 ----------------------------------------------------------- 747 */ 748 ETree * 749 ETree_compress ( 750 ETree *etree, 751 IV *frontmapIV 752 ) ; 753 /*--------------------------------------------------------------------*/ 754 /* 755 ------------------------------------------------------------------------ 756 ----- methods founds in justify.c -------------------------------------- 757 ------------------------------------------------------------------------ 758 */ 759 /* 760 ------------------------------------------------------------ 761 left-justify a tree by subtree size 762 children are linked in ascending order of their subtree size 763 764 created -- 96jan11, cca 765 ------------------------------------------------------------ 766 */ 767 void 768 ETree_leftJustify ( 769 ETree *etree 770 ) ; 771 /* 772 ------------------------------------------------------ 773 left-justify a etree by a metric 774 children are linked in ascending order of their metric 775 776 created -- 96jan11, cca 777 ------------------------------------------------------ 778 */ 779 void 780 ETree_leftJustifyI ( 781 ETree *etree, 782 IV *metricIV 783 ) ; 784 /* 785 ------------------------------------------------------ 786 left-justify a etree by a metric 787 children are linked in ascending order of their metric 788 789 created -- 96jan11, cca 790 ------------------------------------------------------ 791 */ 792 void 793 ETree_leftJustifyD ( 794 ETree *etree, 795 DV *metricDV 796 ) ; 797 /*--------------------------------------------------------------------*/ 798 /* 799 ------------------------------------------------------------------------ 800 ----- methods founds in metrics.c -------------------------------------- 801 ------------------------------------------------------------------------ 802 */ 803 /* 804 ------------------------------------ 805 return an IV object with the weights 806 of the vertices in each front. 807 808 created -- 96jun23, cca 809 ------------------------------------ 810 */ 811 IV * 812 ETree_nvtxMetric ( 813 ETree *etree 814 ) ; 815 /* 816 --------------------------------------------------------------- 817 return an IV object with the number 818 of factor entries in each front. 819 820 symflag -- symmetryflag 821 SPOOLES_SYMMETRIC, SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 822 823 created -- 96jun23, cca 824 --------------------------------------------------------------- 825 */ 826 IV * 827 ETree_nentMetric ( 828 ETree *etree, 829 int flag 830 ) ; 831 /* 832 --------------------------------------------------------------- 833 return a DV object with the number 834 of factor operations in each front. 835 836 type -- type of entries, 837 SPOOLES_REAL or SPOOLES_COMPLEX 838 839 symflag -- symmetryflag, 840 SPOOLES_SYMMETRIC, SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 841 842 created -- 96jun23, cca 843 --------------------------------------------------------------- 844 */ 845 DV * 846 ETree_nopsMetric ( 847 ETree *etree, 848 int type, 849 int symflag 850 ) ; 851 /*--------------------------------------------------------------------*/ 852 /* 853 ------------------------------------------------------------------------ 854 ----- methods founds in stages.c --------------------------------------- 855 ------------------------------------------------------------------------ 856 */ 857 /* 858 ------------------------------------------------------------------- 859 generate a stages vector to be used by the CMD object. 860 (1) if v = par[u] then 861 stages[v] >= stages[u] 862 endif 863 (2) if v is a leaf then 864 stages[v] = 0 865 endif 866 (3) if u and v belong to the same fundamental supernode then 867 stages[v] = stages[u] 868 endif 869 870 basically, all nodes in a domain (a subtree) have stage zero, 871 and the stages of all fundamental supernodes ancestor to that 872 subtree are distinct. 873 874 input -- 875 876 msIV -- IV object that contains the vertices in the 877 multisector (non-domain vertices) 878 879 return value -- 880 881 stagesIV -- an IV object that contains the stage for each vertex 882 883 created -- 96feb19, cca 884 ------------------------------------------------------------------- 885 */ 886 IV * 887 ETree_stagesViaMS ( 888 ETree *etree, 889 IV *msIV 890 ) ; 891 /*--------------------------------------------------------------------*/ 892 /* 893 ------------------------------------------------------------------------ 894 ----- methods founds in transform.c ------------------------------------ 895 ------------------------------------------------------------------------ 896 */ 897 /* 898 ------------------------------------------------------ 899 transform an ETree object by 900 (1) merging small fronts into larger fronts 901 using the ETree_mergeFrontsOne() method 902 (2) merging small fronts into larger fronts 903 using the ETree_mergeFrontsAll() method 904 (3) merging small fronts into larger fronts 905 using the ETree_mergeFrontsAny() method 906 (4) split a large front into a chain of smaller fronts 907 using the ETree_splitFronts() method 908 909 created -- 96jun27, cca 910 ------------------------------------------------------ 911 */ 912 ETree * 913 ETree_transform ( 914 ETree *etree, 915 int vwghts[], 916 int maxzeros, 917 int maxfrontsize, 918 int seed 919 ) ; 920 /* 921 ------------------------------------------------------ 922 transform an ETree object by 923 (1) merging small fronts into larger fronts 924 using the ETree_mergeFrontsOne() method 925 (2) merging small fronts into larger fronts 926 using the ETree_mergeFrontsAll() method 927 (3) split a large front into a chain of smaller fronts 928 using the ETree_splitFronts() method 929 930 created -- 96jun27, cca 931 ------------------------------------------------------ 932 */ 933 ETree * 934 ETree_transform2 ( 935 ETree *etree, 936 int vwghts[], 937 int maxzeros, 938 int maxfrontsize, 939 int seed 940 ) ; 941 /* 942 -------------------------------------------------------------------- 943 purpose -- merge the front tree allowing only chains of nodes to 944 merge that create at most maxzeros zero entries inside a front 945 946 return -- 947 IV object that has the old front to new front map 948 949 created -- 98jan29, cca 950 -------------------------------------------------------------------- 951 */ 952 ETree * 953 ETree_mergeFrontsOne ( 954 ETree *etree, 955 int maxzeros, 956 IV *nzerosIV 957 ) ; 958 /* 959 ------------------------------------------------------- 960 purpose -- merge the front tree allowing a parent 961 to absorb all children when that creates 962 at most maxzeros zero entries inside a front 963 964 return -- 965 IV object that has the old front to new front map 966 967 created -- 98jan29, cca 968 ------------------------------------------------------- 969 */ 970 ETree * 971 ETree_mergeFrontsAll ( 972 ETree *etree, 973 int maxzeros, 974 IV *nzerosIV 975 ) ; 976 /* 977 -------------------------------------------------------------------- 978 purpose -- merge the front tree allowing at most 979 maxzeros zero entries inside a front 980 981 return -- 982 IV object that has the old front to new front map 983 984 created -- 96jun23, cca 985 modified -- 97dec18, cca 986 bug fixed that incorrectly counted the number of zeros in a front 987 -------------------------------------------------------------------- 988 */ 989 ETree * 990 ETree_mergeFrontsAny ( 991 ETree *etree, 992 int maxzeros, 993 IV *nzerosIV 994 ) ; 995 /* 996 ------------------------------------------------- 997 expand an ETree object by splitting a large front 998 into a chain of smaller fronts. 999 1000 created -- 96jun27, cca 1001 ------------------------------------------------- 1002 */ 1003 ETree * 1004 ETree_splitFronts ( 1005 ETree *etree, 1006 int vwghts[], 1007 int maxfrontsize, 1008 int seed 1009 ) ; 1010 /*--------------------------------------------------------------------*/ 1011 /* 1012 ------------------------------------------------------------------------ 1013 ----- methods founds in maps.c ----------------------------------------- 1014 ------------------------------------------------------------------------ 1015 */ 1016 /* 1017 -------------------------------------------------------------- 1018 this method constructs and returns an IV object that holds the 1019 map from fronts to threads for a wrap map of the front tree. 1020 1021 created -- 96dec12, cca 1022 -------------------------------------------------------------- 1023 */ 1024 IV * 1025 ETree_wrapMap ( 1026 ETree *frontTree, 1027 int type, 1028 int symflag, 1029 DV *cumopsDV 1030 ) ; 1031 /* 1032 ---------------------------------------------------------------- 1033 this method constructs and returns an IV object that holds the 1034 map from fronts to threads for a balanced map of the front tree. 1035 the fronts are visited in the post-order traversal. 1036 1037 created -- 96dec12, cca 1038 ---------------------------------------------------------------- 1039 */ 1040 IV * 1041 ETree_balancedMap ( 1042 ETree *frontTree, 1043 int type, 1044 int symflag, 1045 DV *cumopsDV 1046 ) ; 1047 /* 1048 ----------------------------------------------- 1049 this method constructs and returns an IV object 1050 that holds the map from fronts to threads for a 1051 "subtree-subset" map of the front tree. 1052 1053 created -- 97jan15, cca 1054 ----------------------------------------------- 1055 */ 1056 IV * 1057 ETree_subtreeSubsetMap ( 1058 ETree *frontTree, 1059 int type, 1060 int symflag, 1061 DV *cumopsDV 1062 ) ; 1063 /* 1064 ---------------------------------------------------------------- 1065 this method constructs and returns an IV object that holds the 1066 map from fronts to threads for a domain decomposition 1067 balanced map of the front tree. 1068 the domains are mapped to threads using a balanced map, 1069 and the schur complement fronts are mapped to threads 1070 using a balanced map, but the two balanced maps are independent. 1071 1072 created -- 97jan17, cca 1073 ---------------------------------------------------------------- 1074 */ 1075 IV * 1076 ETree_ddMap ( 1077 ETree *frontTree, 1078 int type, 1079 int symflag, 1080 DV *cumopsDV, 1081 double cutoff 1082 ) ; 1083 /* 1084 ---------------------------------------------------------------- 1085 this method constructs and returns an IV object that holds the 1086 map from fronts to threads for a domain decomposition 1087 balanced map of the front tree. 1088 the domains are mapped to threads using a balanced map, 1089 and the schur complement fronts are mapped to threads 1090 using a balanced map, but the two balanced maps are independent. 1091 1092 created -- 97jan17, cca 1093 ---------------------------------------------------------------- 1094 */ 1095 IV * 1096 ETree_ddMapNew ( 1097 ETree *frontTree, 1098 int type, 1099 int symflag, 1100 IV *msIV, 1101 DV *cumopsDV 1102 ) ; 1103 /*--------------------------------------------------------------------*/ 1104 /* 1105 ------------------------------------------------------------------------ 1106 ----- methods founds in splice.c --------------------------------------- 1107 ------------------------------------------------------------------------ 1108 */ 1109 /* 1110 ------------------------------------------------------------- 1111 this method is used to splice together two front trees 1112 when the domain vertices and schur complement vertices 1113 have been ordered separately. 1114 1115 etree0 -- the lower front tree is for vertices in the domain. 1116 graph0 -- graph for all the vertices 1117 mapIV -- IV object that maps vertices to schur complement 1118 vertices, if IV_entry(mapIV, v) < 0 then v is 1119 a domain vertex. 1120 etree1 -- the upper front tree is for vertices in the schur 1121 complement. 1122 1123 created -- 97feb01, cca 1124 ------------------------------------------------------------- 1125 */ 1126 ETree * 1127 ETree_spliceTwoETrees ( 1128 ETree *etree0, 1129 Graph *graph0, 1130 IV *mapIV, 1131 ETree *etree1 1132 ) ; 1133 /*--------------------------------------------------------------------*/ 1134 /* 1135 ------------------------------------------------------------------------ 1136 ----- methods founds in initFromSubtree.c ------------------------------ 1137 ------------------------------------------------------------------------ 1138 */ 1139 /* 1140 ----------------------------------------------------------- 1141 purpose -- to initialize subtree with the subtree 1142 of the front tree using nodes in nodeidsIV. 1143 vtxIV is filled with the vertices in the subtree 1144 1145 return values --- 1146 1 -- normal return 1147 -1 -- subtree is NULL 1148 -2 -- nodeidsIV is NULL 1149 -3 -- etree is NULL 1150 -4 -- nodeidsIV is invalid 1151 -5 -- vtxIV is NULL 1152 1153 created -- 98oct15, cca 1154 ----------------------------------------------------------- 1155 */ 1156 int 1157 ETree_initFromSubtree ( 1158 ETree *subtree, 1159 IV *nodeidsIV, 1160 ETree *etree, 1161 IV *vtxIV 1162 ) ; 1163 /*--------------------------------------------------------------------*/ 1164 /* 1165 ------------------------------------------------------------------------ 1166 ----- methods founds in semi.c ----------------------------------------- 1167 ------------------------------------------------------------------------ 1168 */ 1169 /* 1170 ----------------------------------------------------- 1171 purpose -- 1172 1173 to find the optimal domain/schur complement partition 1174 for a semi-implict factorization. 1175 1176 the gain of a subtree sbt(J) is equal to 1177 1178 |L_{bnd{J},sbt{J}}| - |A_{bnd{J},sbt{J}}| 1179 - alpha *|L_{sbt{J},sbt{J}}| 1180 1181 when alpha = 0 we minimize active storage 1182 when alpha = 1 we minimize solve operations 1183 1184 *ptotalgain is filled with the total gain 1185 1186 the return value is compidsIV, 1187 compids[J] = 0 --> J is in the schur complement 1188 compids[J] != 0 --> J is in domain compids[J] 1189 1190 created -- 98jun20, cca 1191 ----------------------------------------------------- 1192 */ 1193 IV * 1194 ETree_optPart ( 1195 ETree *etree, 1196 Graph *graph, 1197 IVL *symbfacIVL, 1198 double alpha, 1199 int *ptotalgain, 1200 int msglvl, 1201 FILE *msgFile 1202 ) ; 1203 /*--------------------------------------------------------------------*/ 1204 /* 1205 ------------------------------------------------------------------------ 1206 ----- methods founds in storage.c -------------------------------------- 1207 ------------------------------------------------------------------------ 1208 */ 1209 /* 1210 --------------------------------------------------------------- 1211 purpose -- fill dvec[J] with the active storage to eliminate J 1212 using the multifrontal method 1213 1214 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC, 1215 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 1216 1217 created -- 97may21, cca 1218 --------------------------------------------------------------- 1219 */ 1220 void 1221 ETree_MFstackProfile ( 1222 ETree *etree, 1223 int symflag, 1224 double dvec[] 1225 ) ; 1226 /* 1227 --------------------------------------------------------------- 1228 purpose -- fill dvec[J] with the active storage to eliminate J 1229 using the left-looking general sparse method 1230 1231 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC, 1232 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 1233 1234 created -- 97may21, cca 1235 --------------------------------------------------------------- 1236 */ 1237 void 1238 ETree_GSstorageProfile ( 1239 ETree *etree, 1240 int symflag, 1241 IVL *symbfacIVL, 1242 int *vwghts, 1243 double dvec[] 1244 ) ; 1245 /* 1246 --------------------------------------------------------------- 1247 purpose -- fill dvec[J] with the active storage to eliminate J 1248 using the right-looking general sparse method 1249 1250 symflag -- symmetry flag, one of SPOOLES_SYMMETRIC, 1251 SPOOLES_HERMITIAN or SPOOLES_NONSYMMETRIC 1252 1253 created -- 98dec19, cca 1254 --------------------------------------------------------------- 1255 */ 1256 void 1257 ETree_FSstorageProfile ( 1258 ETree *etree, 1259 int symflag, 1260 IVL *symbfacIVL, 1261 double dvec[] 1262 ) ; 1263 /* 1264 --------------------------------------------------------------- 1265 purpose -- fill dvec[J] with the stack storage to solve for J 1266 in a forward solve 1267 1268 created -- 97nov30, cca 1269 --------------------------------------------------------------- 1270 */ 1271 void 1272 ETree_forwSolveProfile ( 1273 ETree *etree, 1274 double dvec[] 1275 ) ; 1276 /* 1277 --------------------------------------------------------------- 1278 purpose -- fill dvec[J] with the stack storage to solve for J 1279 in a backward solve 1280 1281 created -- 97nov30, cca 1282 --------------------------------------------------------------- 1283 */ 1284 void 1285 ETree_backSolveProfile ( 1286 ETree *etree, 1287 double dvec[] 1288 ) ; 1289 /*--------------------------------------------------------------------*/ 1290 /* 1291 ------------------------------------------------------------------------ 1292 ----- methods founds in IO.c ------------------------------------------- 1293 ------------------------------------------------------------------------ 1294 */ 1295 /* 1296 ------------------------------------------------- 1297 purpose -- to read in an ETree object from a file 1298 1299 input -- 1300 1301 fn -- filename, must be *.etreeb or *.etreef 1302 1303 return value -- 1 if success, 0 if failure 1304 1305 created -- 95nov15, cca 1306 ------------------------------------------------- 1307 */ 1308 int 1309 ETree_readFromFile ( 1310 ETree *etree, 1311 char *fn 1312 ) ; 1313 /* 1314 -------------------------------------------------------- 1315 purpose -- to read an ETree object from a formatted file 1316 1317 return value -- 1 if success, 0 if failure 1318 1319 created -- 95nov15, cca 1320 -------------------------------------------------------- 1321 */ 1322 int 1323 ETree_readFromFormattedFile ( 1324 ETree *etree, 1325 FILE *fp 1326 ) ; 1327 /* 1328 ---------------------------------------------------- 1329 purpose -- to read an ETree object from a binary file 1330 1331 return value -- 1 if success, 0 if failure 1332 1333 created -- 95nov15, cca 1334 ---------------------------------------------------- 1335 */ 1336 int 1337 ETree_readFromBinaryFile ( 1338 ETree *etree, 1339 FILE *fp 1340 ) ; 1341 /* 1342 -------------------------------------------- 1343 purpose -- to write an ETree object to a file 1344 1345 input -- 1346 1347 fn -- filename 1348 *.etreeb -- binary 1349 *.etreef -- formatted 1350 anything else -- for human eye 1351 1352 return value -- 1 if success, 0 otherwise 1353 1354 created -- 95nov15, cca 1355 -------------------------------------------- 1356 */ 1357 int 1358 ETree_writeToFile ( 1359 ETree *etree, 1360 char *fn 1361 ) ; 1362 /* 1363 ------------------------------------------------------ 1364 purpose -- to write an ETree object to a formatted file 1365 1366 return value -- 1 if success, 0 otherwise 1367 1368 created -- 95nov15, cca 1369 ------------------------------------------------------ 1370 */ 1371 int 1372 ETree_writeToFormattedFile ( 1373 ETree *etree, 1374 FILE *fp 1375 ) ; 1376 /* 1377 --------------------------------------------------- 1378 purpose -- to write an ETree object to a binary file 1379 1380 return value -- 1 if success, 0 otherwise 1381 1382 created -- 95nov15, cca 1383 --------------------------------------------------- 1384 */ 1385 int 1386 ETree_writeToBinaryFile ( 1387 ETree *etree, 1388 FILE *fp 1389 ) ; 1390 /* 1391 --------------------------------------------------- 1392 purpose -- to write an ETree object for a human eye 1393 1394 return value -- 1 if success, 0 otherwise 1395 1396 created -- 95nov15, cca 1397 --------------------------------------------------- 1398 */ 1399 int 1400 ETree_writeForHumanEye ( 1401 ETree *etree, 1402 FILE *fp 1403 ) ; 1404 /* 1405 ----------------------------------------------------------- 1406 purpose -- to write out the statistics for the ETree object 1407 1408 return value -- 1 if success, 0 otherwise 1409 1410 created -- 95nov15, cca 1411 ----------------------------------------------------------- 1412 */ 1413 int 1414 ETree_writeStats ( 1415 ETree *etree, 1416 FILE *fp 1417 ) ; 1418 /*--------------------------------------------------------------------*/ 1419