ON EXACT COMPUTATIONAL COMPLEXITY OF TRIANGULAR FACTORIZATION ALGORITHMS FOR GENERAL BANDED MATRICES

Matrix triangular factorizations, as an intermediate step of some algorithms, are widely employed to solve scientific and engineering problems. However, there is no exact and explicit expressions on the computational complexity of triangular factorizations for general banded matrices in literatures so far. In this paper, specific and detailed descriptions on triangular factorization algorithms are presented for general banded matrices, and then by carefully dividing matrix into special blocks and with the help of the mathematical software “Maple”, exact and explicit expressions on the computational complexity of these algorithms are rigorously derived. These theoretical results are helpful for calculating the computational complexity of numerical algorithms that employ triangular factorizations, and also provide guidance for choosing appropriate algorithms for specific problems. Numerical experiments validate the obtained theoretical results.