skip to main content
10.1145/1900008.1900031acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
research-article

A robust ILU preconditioner using constraints diagonal Markowitz

Published: 15 April 2010 Publication History

Abstract

In science and engineering, modeling and simulations are popularly used to gather knowledge and explain a complicated phenomena. These models are typically represented in partial differential equations (PDEs) which can be solved using meshes and sparse matrices. The solution cost of PDEs are dominated by the solution cost of sparse linear systems. Therefore, an efficient sparse linear solver becomes more important with the popularity of scientific modeling and simulations. In this paper, we proposed a robust incomplete LU preconditioning algorithm using constraints diagonal Markowitz. Experimental results with various linear systems show that ILU algorithm using constraints diagonal Markowitz shows better performance and more stable than traditional ILU algorithm with predefined ordering.

References

[1]
P. R. Amestoy, T. A. Davis, and I. S. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886--905, 1996.
[2]
O. Axelsson. Iterative Solution Methods. Cambridge University Press, Cambridge, England, 1994.
[3]
R. Beauwens. Modified incomplete factorization strategies. In O. Axelsson and L. Kolotilina, editors, Preconditioned Conjugate Gradient Methods, Lectures Notes in Mathematics, number 1457. Springer-Verlag, Berlin, Germany, 1990.
[4]
M. Benzi, C. D. Meyer, and M. Tuma. A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM Journal on Scientific Computing, 17(5):1135--1149, 1996.
[5]
E. Chow and Y. Saad. Experimental study of ILU preconditioners for indefinie matrices. Journal of Computational and Applied Mathematics, 85, 1997.
[6]
E. D'Azevedo, P. Forsyth, and W. Tang. Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems. SIAM Journal on Matrix Analysis and Applications, 13(4):944--961, 1992.
[7]
E. D'Azevedo, P. Forsyth, and W. Tang. Towards a cost-effective ILU preconditioner with high level fill. BIT, 32:442--463, 1992.
[8]
I. Duff and J. Koster. The design and use of algorithms for permuting large entries to the diagonal of sparse matricies. SIAM Journal of Matrix Analysis and Applications, 20:889--901, 1999.
[9]
I. Duff and J. Koster. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM Journal of Matrix Analysis and Applications, 22:973--996, 2001.
[10]
I. Duff and J. Koster. MC64: Find permutation that place large entries on the diagonal. Technical report, Harwell Subroutine Library, 2004.
[11]
A. George and J. Liu. The evolution of the minimum degree ordering algorithm. SIAM Review, 31:1--19, 1989.
[12]
A. George and J. W.-H. Liu. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ, USA, 1981.
[13]
J. R. Gilbert and S. Toledo. An assessment of incomplete-LU preconditioners for nonsymmetric linear systems. Informatica (Slovenia), 24(3), 2000.
[14]
A. Grama, G. K. A. Gupta, and V. Kumar. Introduction to Parallel Computing. Addison-Wesley, second edition, 2003.
[15]
M. Heath. Scientific Computing: An Introductory Survey. McGraw Hill, New York, 2002.
[16]
D. Keyes. Terascale Optimal PDE Simulations (TOPS) Center, 2004. http://tops-scidac.org.
[17]
I. Lee, P. Raghavan, and E. NG. Effective preconditioning through ordering interleaved with incomplete factorization. SIAM Journal on Matrix Analysis and Applications, 27:1069--1088, 2006.
[18]
J. W.-H. Liu. Modification of the minimum degree algorithm by multiple elimination. ACM Transactions on Mathematical Software, 11:141--153, 1985.
[19]
T. A. Manteuffel. An incomplete factorization technique for positive definite linear systems. Mathematics of Computation, 34(150):473--497, 1980.
[20]
H. Markowitz. The elimination form of the inverse and its application to linear programming. Management Sci., 3:255--269, 1957.
[21]
N. Munksgaard. Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients. ACM Transaction on Mathematical Software, 6:206--219, 1980.
[22]
E. G. Ng and P. Raghavan. Performance of greedy ordering heuristics for sparse Cholesky factorization. SIAM Journal on Matrix Analysis and Applications, 20(4):902--914, 1999.
[23]
Matrix market. URL: http://math.nist.gov/MatrixMarket/.
[24]
S. Parter. The use of linear graphs in Gaussian elimination. SIAM Review, 3:364--369, 1961.
[25]
D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5:266--283, 1976.
[26]
E. Rothberg and S. C. Eisenstat. Node selection strategies for bottom-up sparse matrix ordering. SIAM Journal on Matrix Analysis and Applications, 19(3):682--695, 1998.
[27]
O. Schenk, S. Rollin, and M. Hagemann. Recent advances in sparse linear solver technology for semiconductor device simulation matrices. In Proceedings of the 2003 International Conference on Simulations of Semiconductor Processes and Devices, pages 103--108, Boston, Cambridge, MA. USA, 2003.
[28]
O. Schenkr, S. Rollin, and A. Gupta. The effects of unsymmetric matrix permutations and scalings in semiconductor device and circuit simulation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23:400--411, 2004.
[29]
W. F. Tinney and J. W. Walker. Direct solutions of sparse network equations by optimally ordered triangular factorization. In Proceedings in IEEE, pages 1801--1809, 1967.
[30]
Z. Zlatev. Use of iterative refinement in the solution of sparse linear systems. SIAM Journal on Numerical Analysis, 19:381--399, 1982.

Cited By

View all
  • (2017)Preconditioners for Parallel Reservoir SimulationProceedings of the International Conference on High Performance Compilation, Computing and Communications10.1145/3069593.3069618(45-49)Online publication date: 22-Mar-2017
  • (2017) Improvement of the prediction of surface ozone concentration over conterminous U.S. by a computationally efficient second‐order R osenbrock solver in CAM 4‐ C hem Journal of Advances in Modeling Earth Systems10.1002/2016MS0008639:1(482-500)Online publication date: 20-Feb-2017

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ACMSE '10: Proceedings of the 48th annual ACM Southeast Conference
April 2010
488 pages
ISBN:9781450300643
DOI:10.1145/1900008
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 April 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. ILU
  2. preconditioner
  3. sparse linear systems
  4. sparse matrix
  5. sparse matrix ordering

Qualifiers

  • Research-article

Conference

ACM SE '10
Sponsor:
ACM SE '10: ACM Southeast Regional Conference
April 15 - 17, 2010
Mississippi, Oxford

Acceptance Rates

ACMSE '10 Paper Acceptance Rate 48 of 94 submissions, 51%;
Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Preconditioners for Parallel Reservoir SimulationProceedings of the International Conference on High Performance Compilation, Computing and Communications10.1145/3069593.3069618(45-49)Online publication date: 22-Mar-2017
  • (2017) Improvement of the prediction of surface ozone concentration over conterminous U.S. by a computationally efficient second‐order R osenbrock solver in CAM 4‐ C hem Journal of Advances in Modeling Earth Systems10.1002/2016MS0008639:1(482-500)Online publication date: 20-Feb-2017

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media