readme

数学算法的实现库。可以实现常见的线性计算。

Currently the makefile is prepared for Linux. 
To install the package GNU-make is required
Other platforms will follow
To build the package simply type ''make all''

sample codes
------------

There are several sample programs located in the subdirectory samples

1. main.c   (default simple driver that can only use GMRES as iterative solver)

   Please change the "default.mk" to compile this driver

   To apply the ILUPACK code to a specific matrix type
   
   "dmain <drop_tolerance> <condest> <elbow_space> <matrix>"        (real case)
   "zmain <drop_tolerance> <condest> <elbow_space> <matrix>"        (complex case)

   There is a softlink from the top level directory to the final binaries in
   "samples/D" (real case) and "sample/Z" (complex case)

   drop_tolerance   is the desired drop tolerance for the ILU. 

   condest          is the bound for the norm of the inverse triangular factors
                    L^{-1} and U^{-1}. It is ensured that ||L^{-1}|| and
                    ||U^{-1}|| don't exceed condest, e.g. 100.
                    It may happen that their norms are much smaller.
                    The effective drop tolerance for the approximate Schur
                    complement is obtained by  drop_tolerance/max_condest,
                    where max_condest is the largest norm of ||L^{-1}|| and
                    ||U^{-1}|| that is observed during the factorization.

   elbow_space      this is the parameter that estimates (in terms of multiple
                    of nnz(A)) how many space may be required by the ILU. Since
                    the core part is FOTRAN77 this can be done using malloc

   matrix           may be any matrix in HARWELL BOEING format


2. mainspd.c 
   similar codes for the symmetric (Hermitian) positive definite case

3. mainsym.c 
   similar codes for the symmetric (Hermitian) indefinite case

4. mainsyms.c 
   similar codes for the complex symmetric indefinite case

5. several old fashioned sample drivers for ILUT, ILUTP,... are also available


Orderings
---------

There are several orderings

RCM     (reverse Cuthill-McKee, SPARSPAK, not distributed but interface 
         provided)

MMD     (minimum degree, SPARSPAK, not distributed but interface provided)

AMD     (approximate minimum degree, UMFPACK V4.3, not distributed but 
         interface provided)

METIS_E (multilevel edge dissection, MeTiS 4.0, not distributed but interface 
         provided)

METIS_N (multilevel node dissection, MeTiS 4.0, not distributed but interface 
         provided)

IND SET (indepedent set strategy taken from ARMS)

FC      (fine/coarse grid partitioning similar to the Ruge/Stueben AMG)

PQ      (ddPQ, unsymmetric ordering improving  partial diagonal dominance and
         sparsity)

MC64_RCM     \
MC64_MMD     |  Maximum weight matching MC64 from HSL (I.S. Duff and J. Koster)
MC64_AMD      > combination of max. w. matching followed by certain 
MC64_METIS_E |  symmetric orderings
MC64_METIS_N /

MWM_RCM     \
MWM_MMD     |  Maximum weight matching MPS from PARDISO (O. Schenk and 
MWM_AMD      > K. Gaertner), combination of max. w. matching followed by
MWM_METIS_E |  certain symmetric orderings
MWM_METIS_N /

symmetric indefinite case: symmetric matchings.

SMC64_RCM     \
SMC64_MMD     |  Maximum weight matching MC64 from HSL (I.S. Duff and J. Koster)
SMC64_AMD      > combination of max. w. matching followed by certain 
SMC64_METIS_E |  symmetric orderings
SMC64_METIS_N /

SMWM_RCM     \
SMWM_MMD     |  Maximum weight matching MPS from PARDISO (O. Schenk and 
SMWM_AMD      > K. Gaertner), combination of max. w. matching followed by
SMWM_METIS_E |  certain symmetric orderings
SMWM_METIS_N /



ILUPACK allows three permutation routines (including scaling)

1. initial preprocessing, applied only once to the initial system

2. regular reordering, applied on as many as possible succeeding levels until
   diagonal pivoting fails

3. final pivoting, used if the regular reordering (using diagonal pivoting)
   fails


for ILUPACK it is recommended to combine different strategies, e.g. 

general case                 1. PERMMC64AMD   (matching + AMD for the initial system)
                             2. PERMAMD       (AMD for any subsystem)
                             3. PERMPQ        (if anything else fails simply use ddPQ)

symmetric indefinite case    1. PERMSMC64AMD  (symmetric matching + AMD for all systems)
                             2. PERMSMC64AMD 
                             3. ---

SPD case                     1. SPDPERMAMD    (AMD for the initial system)
                             2. SPDPERMAMD    (AMD for any subsystem)
                             3. SPDPERMPP     (if anything else fails use SPD ddPQ)



Each of the reordering+scaling drivers can be chosen out of the following list


general case: 
-------------

recommended permutations based on matchings or diagonal dominance:
PERMMC64RCM, PERMMC64MMD, PERMMC64AMD, PERMMC64METISE, PERMMC64METISN, 
PERMMWMRCM,  PERMMWMMMD,  PERMMWMAMD,  PERMMWMMETISE,  PERMMWMMETISN, 
PERMPQ, 

permutations without improving diagonal dominances (be sure your matrix does have enough
structure that diagonal dominance does not need to be improved):
PERMNULL,    PERMINDSET,  PERMFC,      
PERMRCM,     PERMMMD,     PERMAMD,     PERMMETISE,     PERMMETISN,



symmetric indefinite case:
--------------------------

recommended permutations based on symmetric matchings:
PERMSMC64RCM, PERMSMC64MMD, PERMSMC64AMD, PERMSMC64METISE, PERMSMC64METISN, 
PERMSMWMRCM,  PERMSMWMMMD,  PERMSMWMAMD,  PERMSMWMMETISE,  PERMSMWMMETISN, 

permutations without matchings (NOT recommended, this will lead to poor preconditioners):
SYMPERMNULL,    SYMPERMINDSET,  SYMPERMFC,      
SYMPERMRCM,     SYMPERMMMD,     SYMPERMAMD,     SYMPERMMETISE,     SYMPERMMETISN,


SPD case:
---------

SYMPERMNULL,    SYMPERMINDSET,  SYMPERMFC,      SPDPERMPP,
SYMPERMRCM,     SYMPERMMMD,     SYMPERMAMD,     SYMPERMMETISE,     SYMPERMMETISN,


The sample codes offer some combinations that always use PERMPQ as final
pivoting strategy





Switches
--------

Several switches are supported

1. different approximate Schur complements
   SIMPLE_SC       the leading block and the remaining approximate Schur
   (default)       complement are computed with single drop tolerance
                   precision
   TISMENETSKY_SC  the leading block and the remaining approximate Schur
                   complement are computed with double drop tolerance
                   precision (squared).
                   More accurate but much more memory required and may be
                   significantly slower
   ~SIMPLE_SC      the leading block is computed using single drop
                   tolerance precision but the remaining approximate Schur
                   complement are computed with double drop tolerance precision

2. DIAGONAL_COMPENSATION applies diagonal compensation

3. ENSURE_SPD      (default in the SPD case) ensures that dropping does not
                    destroy the positive definiteness

4. IMPROVED_ESTIMATE (default) improved estimate for the inverse factors

5. DROP_INVERSE    (default) inverse-based factorization

6. COARSE_REDUCE   (default) clean up the LU factors from the partial ILU

7. FINAL_PIVOTING  indicate that a different strategy is used as third 
                   permutation, only necessary if the third reordering strategy
                   is different from the second one

8. MULTI_PILUC     instead of moving the delayed updates to the next level
                   repeat the factorization multiple times