Linearly scaling direct method for accurately inverting sparse banded matrices

Physics – Computational Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

24 pages, 5 figures, submitted to J. Comp. Phys

Scientific paper

In many problems in Computational Physics and Chemistry, one finds a special kind of sparse matrices, termed "banded matrices". These matrices, which are defined as having non-zero entries only within a given distance from the main diagonal, need often 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, being n X n the size of the matrix. We produce the analytical recursive expressions that allow to directly obtain the solution, as well as the pseudocode for its computer implementation. Moreover, we review the different options for possibly parallelizing the method, we describe the extension to deal with matrices that are banded plus a small number of non-zero entries outside the band, and we use the same ideas to produce a method for obtaining the full inverse matrix. Finally, we show that the New Algorithm is competitive, both in accuracy and in numerical efficiency, when compared to a standard method based in Gaussian elimination. We do this using sets of large random banded matrices, as well as the ones that appear when one tries to solve the 1D Poisson equation by finite differences.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Linearly scaling direct method for accurately inverting sparse banded matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linearly scaling direct method for accurately inverting sparse banded matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linearly scaling direct method for accurately inverting sparse banded matrices will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-474233

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.