looking for fastest algorithm for solving banded systems of equations

From: Michael Weitzel (weitzel_at_simtec.mb.uni-siegen.de)
Date: 03/21/05 

Date: 21 Mar 2005 14:43:57 +0200

Hi,

I am working with banded systems of linear equations. These systems are
characterized by matrix dimension N, a lower bandwith[1] lb and an upper
bandwidth ub (overall bandwidth is lb+1+ub).

Apart from the bandwidth and the fact that the system has full rank, there
are no other special properties (such as positive definiteness or symmetry).

 * What is the running time (in terms of \Theta, asymtotic tight bound) of
   the fastest algorithm from the Gauss/LU(P) algorithm-family?
 * Is there a known algorithm that is faster than O(N^2) and only quadratic
   in bandwidth but not in matrix dimension? ( i.e. O(N*(lb+1+ub)^2 )

Thanks for your help!

[1] The term bandwidth means, given a matrix A with Elements A(i,j),
    A(i,j) = 0 where i>j+lb or j>i+ub for 1<=i,j<=N, i.e. the only
    non-zero elements are in a band of width lb+1+ub around the diagonal

Relevant Pages

  • Re: POWER7 information - global shared memory, eDRAM for cache
    ... efficiently pack/transmit data to better use bandwidth. ... graph theoretic algorithm are like that, ... a theoretically slower but better behaved algorithm, ... It depends on the type of data dependencies. ...
    (comp.arch)
  • Bandwidth selection for kernel intensity estimation
    ... Is there a variant of the Sheather-Jones bandwidth selection algorithm ... for kernel density estimation that works for estimating an intensity ...
    (sci.stat.consult)
  • Re: Oversampling and receiver
    ... Lets say that my tx use a raised cosine filter to limit the bandwidth ... clock recovery is better solution. ... Gardner algorithm or other algorithm that use non-linear tranformation to ...
    (comp.dsp)
  • Re: tamper resistant messages on 8051
    ... eugene wrote: ... If you only have two bytes of bandwidth, your attacker only has to try ... algorithm like Microchip's Keeloq (note that it is patented, ...
    (comp.arch.embedded)