Incomplete LU algorithms for C++ and Python
Project description
ilupp  ILU algorithms for C++ and Python
Copyright (C) 2020 Clemens Hofreither
ILU++ is Copyright (C) 2006 by Jan Mayer
$ pip install ilupp
This project provides C++ implementations and Python bindings for many incomplete LU and incomplete Cholesky algorithms. It is based on the original ILU++ package described in the publication
 Mayer, J. (2007), ILU++: A new software package for solving sparse linear systems with iterative methods. Proc. Appl. Math. Mech., 7: 20201232020124. doi:10.1002/pamm.200700911
Compared to the original ILU++, this package has been significantly improved:
 Code cleaned up and modernized for C++11
 Extensive test suite
 Many critical bugs fixed
 Massive performance improvements (orders of magnitude for large matrices)
 Added several new factorizations, like ILU(0), IChol(0), and incomplete Cholesky with choosable fillin and thresholding
It also contains the multilevel Crout ILU preconditioner described in (Mayer 2007).
The original ILU++ homepage is no longer available, although it can still be accessed via archive.org:
The original ILU++ had little documentation beyond some comments in the source code. Nevertheless, the Python bindings provide a simple interface to either solve a linear system in a blackbox way, or to compute a preconditioner and apply it to a vector. In both cases, the matrix should be provided as a Scipy CSR or CSC matrix.
Below there is a reproduction of the most relevant parts of the original homepage.
Choosing the Right Combination of Preprocessing and Preconditioner
The standard multilevel preconditioner of ILU++ depends on a larger number of parameters and it can be combined with many different preprocessing techniques. An overview can be found in the files orderings.h and parameters.h (and the respective implementation files). ILU++ offers several default configurations of such combinations. These configurations have been successful for a large number of problems. Hence, they are good place to start before experimenting with the parameters yourself. For easy access, the default configurations are numbered. Note that the different configurations for the preconditioner (i.e. the multilevel incomplete LU factorization) are also numbered, so care must be taken to distinguish between the number of the default configuration and the number of the preconditioner which a particular default configuration uses in combination with preprocessing.
Default Configuration Number 0 (and 1000)
This is implementation is not the first choice of a general purpose solver and is included mostly for compatibility with previous releases. For each level, the rows and columns of the coefficient matrix are normalized. Subsequently, PQ preprocessing is performed to improve diagonal dominance. The preconditioner (factorization) used is number 0. It pivots by both rows and columns. Column pivoting intends to avoid small pivots, whereas row interchanges are implemented to promote better sparsity. The levels are terminated whenever it appears that continued factorization would result in too much fillin. Default configuration 1000 uses the factorisation 1000 instead of 0, which calculates a sparser Schur complement.
Advantages:
 Good preconditioner, often quite sparse
 Very fast setup times
Disadvantages:
 Memory requirements for intermediate calculations are quite high
Default Configuration Number 10 (and 1010)
This implementation uses the maximal weighted matching and scaling to produce an Imatrix as preprocessing. The factorisation used is number 0, which implements pivoting by columns (to avoid small pivots) and row permutation to reduce fillin. Levels are terminated whenever fillin is too high. This is the best combination overall in terms of total calculation time, but this comes at fairly high memory costs for intermediate calculations. Default configuration 1010 uses the factorisation 1000 instead of 0, which calculates a sparser Schur complement.
Advantages:
 Good preconditioner, often quite sparse
 Fast setup times
Disadvantages:
 Memory requirements for intermediate calculations are quite high
Default Configuration Number 11 (and 1011)
This implementation uses the same preprocessing as default configuration number 10 plus an additional symmetric reordering to produce an initial diagonally dominant submatrix. Consequently, setup times are slightly longer. It uses a different preconditioner (number 10) than the other default configurations. No pivoting is performed at all, reducing the memory requirements for intermediate calculations significantly. Even though this works quite well for most matrices because of the preprocessing, the resulting preconditioner generally needs to be somewhat more dense to be effective. Levels are terminated whenever a pivot becomes too small (by absolute value). Default configuration 1011 uses the factorisation 1010 instead of 10, which calculates a sparser Schur complement.
Advantages:
 Good preconditioner
 Little additional memory is needed for calculations
Disadvantages:
 Longer setup times
 Preconditioner often not as sparse
Theoretical Background
The preconditioning used in ILU++ consists of the following steps:
 Preprocessing
 Partial factorization with dropping to ensure sparsity
 Level termination and calculation of the Schur complement
 Preconditioning of (an approximate) Schur complement using Steps 1 to 4 recursively
Because of 4), a preconditioner generally has several "levels", one corresponding to each matrix (coefficient matrix or Schur complement) being factored. Specifically, ILU++ does the following:
Step 1)
Preprocessing consists of reordering and scaling of rows and columns to make the coefficient matrix more suitable for incomplete factorization. The preprocessing to make an Imatrix is best single method, but best results are generally obtained by combining different preprocessing methods. In particular, using additional methods to improve diagonal dominance of rows and columns having low indices is generally favorable. Preprocessing methods which aim at improving the matrix structurally without taking the elements themselves into account (e.g. Reverse CuthillMcKee, METIS, etc.) often result in little further improvement for the preconditioners implemented in ILU++.
Step 2)
The coefficient matrix A is factored using Crout's implementation of Gaussian elimination, meaning that in the kth step the kth row of U and the kth column of L in the (incomplete) factorization A = LDU is calculated. (D is a diagonal factor containing the pivots; L and U are unit lower and upper triangular matrices.) Pivoting by columns can be used to avoid small pivots and pivoting by rows can be used to eliminate those rows first resulting in the least fillin. Pivoting does, however, require substantially more memory to perform the calculations. If little or no preprocessing is done to improve diagonal dominance, then pivoting is essential for many matrices.
Dropping is performed by default by a rule to (heuristically) reduce the errors in L and U and to reduce the propagation of errors in factorization. For many matrices, even very sparse preconditioners result in convergent iterations. For other dropping rules, such sparse preconditioners generally fail. For more difficult matrices, ensuring small errors in the inverses of L and U is more important. Hence, inversebased dropping (as used for example in ILUPACK) is also available. These preconditioners generally require more fillin for convergence for most matrices. However, for a few difficult matrices, this dropping rule results in convergence, whereas the default dropping rule does not.
Step 3)
After the calculation of the kth step has been completed, it is possible to stop calculating L, D and U and to proceed to calculating (a sparse approximation of) the Schur complement of A instead. Three possibilities for terminating a level have been implemented:
 stop whenever the preprocessing indicates
 stop whenever fillin becomes too high
 stop whenever the absolute value of the pivot becomes too small
Some preprocessing techniques provide a natural point to terminate a level, (e.g. PQreordering attempts to improve diagonal dominance and yields a row index, upto which this was successful). Whenever pivoting by rows is performed, rows are eliminated (heuristically) in the order "of increasing fillin". Hence, it is possible to terminate a level, whenever the expected fillin becomes too high. Finally, whenever no pivoting is performed then small pivots (in absolute value) are a particular concern (even if preprocessing has resulted in reasonably good diagonal dominance). In this situation, terminating a level whenever the pivots become too small (in absolute value) works well.
Further Details and Citing ILU++
Further details can be found in
Mayer, Jan: A Multilevel Crout ILU Preconditioner with Pivoting and Row Permutation. To appear in Numerical Linear Algebra with Applications.
Mayer, Jan: Symmetric Permutations for Imatrices to Delay and Avoid Small Pivots During Factorization. To appear in SIAM J. Sci. Comput.
and in the literature cited in these papers.
Preprints are available upon request from jan.mayer@mathematik.unikarlsruhe.de
If you are using ILU++ for your scientific work, please cite these papers and the ILU++ website http://iamlasun8.mathematik.unikarlsruhe.de/~ae04/iluplusplus.html.
Project details
Release history Release notifications
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size ilupp1.0.1cp35cp35mmanylinux1_x86_64.whl (1.9 MB)  File type Wheel  Python version cp35  Upload date  Hashes View 
Filename, size ilupp1.0.1cp35cp35mmanylinux2010_x86_64.whl (3.3 MB)  File type Wheel  Python version cp35  Upload date  Hashes View 
Filename, size ilupp1.0.1cp35cp35mwin32.whl (209.1 kB)  File type Wheel  Python version cp35  Upload date  Hashes View 
Filename, size ilupp1.0.1cp35cp35mwin_amd64.whl (258.0 kB)  File type Wheel  Python version cp35  Upload date  Hashes View 
Filename, size ilupp1.0.1cp36cp36mmanylinux1_x86_64.whl (1.9 MB)  File type Wheel  Python version cp36  Upload date  Hashes View 
Filename, size ilupp1.0.1cp36cp36mmanylinux2010_x86_64.whl (3.3 MB)  File type Wheel  Python version cp36  Upload date  Hashes View 
Filename, size ilupp1.0.1cp36cp36mwin32.whl (215.5 kB)  File type Wheel  Python version cp36  Upload date  Hashes View 
Filename, size ilupp1.0.1cp36cp36mwin_amd64.whl (264.5 kB)  File type Wheel  Python version cp36  Upload date  Hashes View 
Filename, size ilupp1.0.1cp37cp37mmanylinux1_x86_64.whl (1.9 MB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size ilupp1.0.1cp37cp37mmanylinux2010_x86_64.whl (3.3 MB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size ilupp1.0.1cp37cp37mwin32.whl (215.5 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size ilupp1.0.1cp37cp37mwin_amd64.whl (264.5 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size ilupp1.0.1cp38cp38manylinux1_x86_64.whl (1.9 MB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size ilupp1.0.1cp38cp38manylinux2010_x86_64.whl (3.3 MB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size ilupp1.0.1.tar.gz (416.2 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for ilupp1.0.1cp35cp35mmanylinux1_x86_64.whl
Algorithm  Hash digest  

SHA256  ec1e0d4d1a64e5deebe1c93246edd1cc88657bb9f8b38bff9466b7ba50e96d5f 

MD5  bc6f648b2594a05c5658f82f20a0bace 

BLAKE2256  db022cb9a03ceb5139f3d7c4bc4159b086fc7a51f97c9cc7f0122c4a07add6bc 
Hashes for ilupp1.0.1cp35cp35mmanylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  7f98ec5033c23fe0a6bae75cbba7d41f733805a33f0956b8ab9ec64ea762d4ec 

MD5  c73a66e69123d4cfca89823bce1f42dc 

BLAKE2256  d41fc88c010b5280cf3c19cd86e38e234bcd630db7ab59cfbe94ee333d35c3dc 
Hashes for ilupp1.0.1cp35cp35mwin32.whl
Algorithm  Hash digest  

SHA256  a897cf1977265aad51219828dae9efc3201d76928e1e6079775603090ec433ee 

MD5  64941bf92db959b12ef9bf6ff11375ed 

BLAKE2256  49b224d8cbea5f1d208037a44589b687f2a7f1e54613d66ab6d0f03bc1435c7e 
Hashes for ilupp1.0.1cp35cp35mwin_amd64.whl
Algorithm  Hash digest  

SHA256  ceac2daa3276bfa66625c9caca7d8acbe28fe3d4d943fc07cdb4d770d98a048e 

MD5  d6f8fb4ac33aa9517a2c6596d31806e7 

BLAKE2256  2215bb1f43c2be300c5bfddccf37ad8c904355f47ce8ff6ce6464dd7b878a302 
Hashes for ilupp1.0.1cp36cp36mmanylinux1_x86_64.whl
Algorithm  Hash digest  

SHA256  076b20eaab358880e8c67606463ff03af02ce9845661ec7dd0c8dda76933ebbc 

MD5  522c0238e392d0ddf258f3149d1d8665 

BLAKE2256  1fae70aaba199f6eb669a53cbfe7fb46adfa2f337e0d58f099323c7972d47c14 
Hashes for ilupp1.0.1cp36cp36mmanylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  1149345ef4a453d3573fb70918d9a11d910afb4ceedeff780226074963a1f429 

MD5  aec087de9b3b4fc897730faf1d536d23 

BLAKE2256  7b3634cbaee78e22e614a219c9c79fe1f99efeae4d0c23a8bc27e2ab545705ae 
Hashes for ilupp1.0.1cp36cp36mwin32.whl
Algorithm  Hash digest  

SHA256  fc4138bded94804324a0663b791c2a5b1a0e4764eb771e35a9e56d6d49d5df5b 

MD5  811c18b769d1e53a2581b409c7b50fd3 

BLAKE2256  aaf6370ad30d206ed4f958f6d06f3430e126baf80f7676fda85cc65f759c317f 
Hashes for ilupp1.0.1cp36cp36mwin_amd64.whl
Algorithm  Hash digest  

SHA256  cecc37dd10b18a1a7386325dcda29e97682edbaa79ccb9bdf23d321ec24edbb2 

MD5  04267b1a99cfe02d5f8e81de6df0fe09 

BLAKE2256  6baeb6801a432a44ecfac35931c7f7b07a01d757183f32d8064eaaf109f70a6a 
Hashes for ilupp1.0.1cp37cp37mmanylinux1_x86_64.whl
Algorithm  Hash digest  

SHA256  b919343b0ca6f289e601cacc2d917d882b1453042ef165edb062a8c55b4cbbfb 

MD5  dc82274f8e96bdaa5cacedce5abd6d94 

BLAKE2256  b77e073ca92c8fe09bd31d237e567dc52e4948579c12f851b7da2cbdd2ea1172 
Hashes for ilupp1.0.1cp37cp37mmanylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  4ab1644a96ec564f0a5568737216a289da29c8a59c911a72c0f19f534722b035 

MD5  0e9ca419d17aec05c9dbf25aa244bc89 

BLAKE2256  25c740a235ed417b5a0260f346fe3ae4aa5cd22139a224643d0fca11371e6c3c 
Hashes for ilupp1.0.1cp37cp37mwin32.whl
Algorithm  Hash digest  

SHA256  a4351fa4995cc2c85d41a71fccdcf2f85101d1c17ef57e483aba059790127368 

MD5  ca3e5f60c389559c7de93d8b94773953 

BLAKE2256  0a2a1e4a2158081cd5dc32012ae2a0158e573f2411753eaf845961b00f6839c9 
Hashes for ilupp1.0.1cp37cp37mwin_amd64.whl
Algorithm  Hash digest  

SHA256  05370a4f0c5368aba05eacc84a2a0ed0761d8fe49cf276ef2d903036491c8188 

MD5  d65375db90ab2d8daee3af6caeb77bda 

BLAKE2256  142f23eafd274a466e233442a10516e0a8ea2520fd0ef6af037e8e9083222059 
Hashes for ilupp1.0.1cp38cp38manylinux1_x86_64.whl
Algorithm  Hash digest  

SHA256  3e9cd142f6e54d945a6853549b01e28b2b5131ca0241a944940971db98592070 

MD5  def71b0a30625f14a7173060af339b9a 

BLAKE2256  db6127c7be163cc909b055f445c4dd27c9f67c2a1a22e6287f0a85aacf0d95cb 
Hashes for ilupp1.0.1cp38cp38manylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  95cdd701c1cc9029eeadcc3d5dd71a1b41d56c8cc3410b71837ffee5cb71a4c7 

MD5  8cb23817b0fefa7b1bcdd1d746fa768e 

BLAKE2256  f3111687609215fc692d2cc3ac96bd217eeee720df275c23a8338cc1205ab6e5 