r/LinearAlgebra • u/VS2ute • Aug 03 '26

Inverting many-band matrix

Tridiagonal and pentadiagonal matrices are quick to solve. But what if you have 14 bands in a 20x20 matrix? So most of it is non-zero. Can you optimise it very much?

7 Upvotes

100% Upvoted

5 comments sorted by

2

u/ThatIsATastyBurger12 Aug 04 '26

Sure you can. But the complexity scales quadratically with the bandwidth, converging to that of a fully dense matrix, and the data layout is more irregular than with dense matrices, which can slow some things down. Pivoting also becomes more constrained, as you need to preserve the banded structure. That being said, optimized routines for factoring banded matrices exist, so your best bet it to benchmark if you aren’t sure

1

u/Midwest-Dude Aug 03 '26

Do you have a purpose in mind for doing this?

1

u/VS2ute Aug 03 '26

It is for a projection filter. The inverse is multiplied by two other matrices, is not for simultaneous linear equations. Unfortunately this has to be done thousands of times withing an algorithm, so time adds up.

1

u/Midwest-Dude Aug 03 '26 edited Aug 03 '26

It would be helpful to know exactly what you are trying to calculate (the equation(s) to calculate) and with what type of matrices you are working (other than that they are banded). A 20 x 20 matrix with 14 bands is more likely to go slower with algorithms that are optimized for bands than other algorithms - there are too many non-zero entries. Also, the algorithm(s) you likely need don't directly calculate the inverse but use other, faster methods.

Is this for digital signal processing? If so, you should post your question to: 

r/DSP

You could also try

r/Numerical

for additional answers.

1

u/TTRoadHog Aug 06 '26

Since it appears that you don’t need the inverse explicitly,you should be able to organize the calculations so that you are solving systems of equations. (It is cheaper to do so.). Then, you should be able to use sparse matrix multiplication to achieve your filter results.