Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Num. Meth. Prog., 2014, Volume 15, Issue 3, Pages 441–460 (Mi vmp263)  

This article is cited in 1 scientific paper (total in 1 paper)

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

S. A. Solovyev

A. A. Trofimuk Institute of Petroleum Geology and Geophysics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

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.

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

Full text: PDF file (1212 kB)
UDC: 519.612
Received: 22.05.2014

Citation: S. A. Solovyev, “Application of the low-rank approximation technique in the Gauss elimination method for sparse linear systems”, Num. Meth. Prog., 15:3 (2014), 441–460

Citation in format AMSBIB
\Bibitem{Sol14}
\by S.~A.~Solovyev
\paper Application of the low-rank approximation technique in the Gauss elimination method for sparse linear systems
\jour Num. Meth. Prog.
\yr 2014
\vol 15
\issue 3
\pages 441--460
\mathnet{http://mi.mathnet.ru/vmp263}


Linking options:
  • http://mi.mathnet.ru/eng/vmp263
  • http://mi.mathnet.ru/eng/vmp/v15/i3/p441

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. B. Sviridenko, “Pryamye multiplikativnye metody dlya razrezhennykh matrits. Nesimmetrichnye lineinye sistemy”, Kompyuternye issledovaniya i modelirovanie, 8:6 (2016), 833–860  mathnet  crossref
  • Numerical methods and programming
    Number of views:
    This page:338
    Full text:140

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022