English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/44505
logo share SHARE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Linearly scaling direct method for accurately inverting sparse banded matrices

AuthorsGarcía-Risueño, Pablo; Echenique, Pablo
linear scaling
banded matrix
lagrange multipliers
Issue Date19-Jan-2012
PublisherInstitute of Physics Publishing
CitationJournal of Physics A: Mathematical and Theoretical 45:065204 (2012)
AbstractIn many problems in computational physics and chemistry, one finds special kinds of sparse matrices, called banded matrices. These matrices, which are defined as having non-zero entries only within a given distance from the main diagonal, often need to be inverted in order to solve the associated linear system of equations. In this work, we introduce a new O(n) algorithm for solving such a system, with the size of the matrix being n X n. We derive analytical recursive expressions that allow us to directly obtain the solution. In addition, we describe the extension to deal with matrices that are banded plus a small number of non-zero entries outside the band, and use the same ideas to produce a method for obtaining the full inverse matrix. Finally, we show that our new algorithm is competitive, both in accuracy and in numerical efficiency, when compared with a standard method based on Gaussian elimination. We do this using sets of large random banded matrices, as well as the ones that appear in the calculation of Lagrange multipliers in proteins.
DescriptionThe definitive publisher authenticated version is available online at http://dx.doi.org/10.1088/1751-8113/45/6/065204
Publisher version (URL)http://dx.doi.org/10.1088/1751-8113/45/6/065204
Appears in Collections:(IQFR) Artículos
Files in This Item:
File Description SizeFormat 
2012_BandedMatricesInversion.pdf2,45 MBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.