Application of the low-rank approximation technique in the Gauss elimination method for sparse linear systems

Authors

  • S.A. Solovyev Trofimuk Institute of Petroleum Geology and Geophysics of SB RAS

Keywords:

three-dimensional problems of mathematical physics, algorithms for sparse linear systems, Gauss elimination method, low-rank approximation, HSS matrix representation, iterative refinement

Abstract

A fast direct algorithm for 3D discretized linear systems using the Gauss elimination method together with the nested dissection ordering approach and low-rank approximations is proposed. This algorithm is described for symmetric positive definite matrices and can be easily extended to the case of nonsymmetric systems. In order to store the factor L in the LU-decomposition of the original matrix, the large-block representation as well as HSS format (Hierarchically Semiseparable Structure) are used. The construction of a low-rank approximation is based on using the adaptive cross approximation (ACA) approach, which is more efficient compared to the SVD and QR methods. In order to enhance the efficiency of the corresponding solver, a number of Intel MKL BLAS and LAPACK subroutines are used. This solver was implemented for shared memory computing systems. The functional testing shows a high quality of low-rank/HSS approximation. The performance testing demonstrates up to 3 times performance gain in comparison with the Intel MKL PARDISO direct solver. The proposed solver allows one to significantly decrease the memory and time consumption while using the Gauss elimination method.

Author Biography

S.A. Solovyev

Trofimuk Institute of Petroleum Geology and Geophysics of SB RAS
• Researcher

References

  1. Бахвалов Н.С. О сходимости одного релаксационного метода при естественных ограничениях на эллиптический оператор // Ж. вычисл. матем. и матем. физ. 1966. 6, № 5. 861-885.
  2. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984.
  3. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.
  4. Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Ж. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
  5. Bebendorf M. Approximation of boundary element matrices // Numer. Mathem. 2000. 86, N 4. 565-589.
  6. Chandrasekaran S., Dewilde P., Gu M., Somasunderam N. On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs // Siam Journal on Matrix Analysis and Applications. 2010. 31, N 5. 2261-2290.
  7. Chandrasekaran S., Gu M., Li X.S., Xia J. Some fast algorithms for hierarchically semiseparable matrices. Report LBNL-62897. Berkeley: Lawrence Berkeley Nat. Lab., 2007.
  8. Chandrasekaran S., Dewilde P., Gu M., Pals T. A fast ULV decomposition solver for hierarchically semiseparable representations // SIAM J. Matrix Anal. Appl. 2006. 28, N 3. 603-622.
  9. Ernst O.G., Gander M.J. Why it is difficult to solve Helmholtz problems with classical iterative methods // Numerical Analysis of Multiscale Problems. Heidelberg: Springer, 2012. 325-363.
  10. George A. Nested dissection of a regular finite element mesh // SIAM Journal on Numerical Analysis 1973. 10, N 2. 345-363.
  11. Lipton R., Rose D., Tarjan R. Generalized nested dissection // SIAM J. Numer. Anal. 1979. 16, N 2. 346-358.
  12. Hackbusch W. A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices // Computing. 1999. 62, N 2. 89-108.
  13. Bebendorf M., Hackbusch W. Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^infty-coefficients // Numer. Mathem. 2003. 95, N 1. 1-28.
  14. Karypis G., Kumar V. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 4.0. Minneapolis: University of Minnesota, 1998.
  15. Le Borne S., Grasedyck L., Kriemann R. Domain-decomposition based H-LU preconditioners // Lecture Notes in Computational Science and Engineering. Vol. 55. Heidelberg: Springer, 2007. 667-674.
  16. Lipton R., Rose D., Tarjan R. Generalized nested dissection // SIAM J. Numer. Anal. 1979. 16, N 2. 346-358.
  17. Ortega J.M. Повторяет ссылку [3]: Introduction to Parallel and Vector Solution of Linear Systems. Frontiers in Computer Science, Springer. 1988.
  18. Rjasanow S. Adaptive cross approximation of dense matrices // Proc. Int. Association for Boundary Element Methods. Austin: Univ. Texas at Austin, 2002. 1-12.
  19. Saad Y. Iterative methods for sparse linear systems. Philadelphia: SIAM, 2003.
  20. Saad Y., Vorst H. Iterative solution of linear systems in the 20th century // Journal of Computational and Applied Mathematics. 2000. 123, N 1. 1-33.
  21. Goreinov S.A., Tyrtyshnikov E.E., Zamarashkin N.L. A theory of pseudo-skeleton approximations // Linear Algebra Appl. 1997. 261, N 1-3. 1-21.
  22. Tyrtyshnikov E.E. Mosaic-skeleton approximations // Calcolo. 1996. 33, N 1. 47-57.
  23. Tyrtyshnikov E.E. Incomplete cross approximation in the mosaic-skeleton method // Computing. 2000. 64, N 4. 367-380.
  24. Wang S., de Hoop M.V., Xia J., Li X.S. Massively parallel structured multifrontal solver for time-harmonic elastic waves in 3-D anisotropic media // Geophys. J. Int. 2012. 191, N 1, 346-366.
  25. Wang S., Li X.S., Xia J., de Hoop M.V., Situ Y. Efficient scalable algorithms for hierarchically semiseparable matrices // SIAM J. Sci. Comput. 2013. 35, N 6. 519-544.
  26. Xia J. A robust inner-outer hierarchically semi-separable preconditioner // Numer. Linear Algebra Appl. 2012. 19, N 6. 992-1016.
  27. Xia J. Efficient structured multifrontal factorization for general large sparse matrices // SIAM J. Scientific Computing. 2013. 35, N 2. 832-860.
  28. Xia J. Robust and efficient multifrontal solver for large discretized PDEs // High-Performance Scientific Computing. London: Springer, 2012. 199-217.
  29. Xia J., Chandrasekaran S., Gu M., Li X.S. Superfast multifrontal method for large structured linear systems of equations // SIAM J. Matrix Anal. Appl. 2009. 31, N 3. 1382-1411.
New computational technologies

Downloads

Published

29-07-2014

How to Cite

Соловьев С. Application of the Low-Rank Approximation Technique in the Gauss Elimination Method for Sparse Linear Systems // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2014. 15. 441-460

Issue

Vol. 15 (2014): Issue 3.

Section

Section 1. Numerical methods and applications