Arithmetic Complexity Of Direct Solvers For Banded Systems

We report on arithmetic complexity of direct solvers for g -semiband n 2 n systems. If GT denotes grand total of all operations of additions, multiplications and divisions, then in each case GT= p ( g ) n m q ( g ), where p ( g ) and q ( g ) are nonnegative polynomials of degree two and three, respectively. If divisors are not saved, GT reported here saves precisely n operations. Partial pivoting for banded systems can increase the operations counts significantly. We give these counts, and for multiple right-hand sides. For g =1 and n m 1, our results agree with known counts. Some interesting observations follow from the obtained counts.

Keywords:

• Banded Systems
• Arithmetic Complexity
• Lu
• Elimination
• Partial Pivoting
• Choleski
• Root-free Symmetric Elimination