I am struggling with the details of the LU factorization algorithm for band matrices implemented in dgbtrf.f. Referring to the comments the partial pivoting (row interchanges) technique is used.
On entry, the caller has to reserve some space for KL (/lower bandwidth) additional diagonals and it's clear why... On exit the routine returns with a LU factorization having THE SAME lower bandwidth KL and the new upper bandwidth KU.
What trick is used here? Why doesn't the lower bandwidth change? A standard LU factorization spoils the lower bandwidth - for example:
- Code: Select all
4x4 matrix A, lower bandwidth 1, upper bandwidth 1
7 7 0 0
7 7 3 0
0 4 8 2
0 0 6 10
step/row 1:
- pivot is A(1,1)=7 (no row interchange)
- divide first column beginning in row 2 through pivot
- compute in A(i=2..4,j=2..4): A(i,j) = A(i,j) - A(i,1)*A(1,j)
- in the example only A(2,2) is affected, resulting in:
7 7 0 0
1 0 3 0
0 4 8 2
0 0 6 10
step/row 2:
- pivot is A(3,2)=4, interchange rows 2 and 3; LOWER BANDWIDTH INCREASES
(upper bandwidth also increases)
- divide second column beginning in row 3 through pivot
- compute in A(i=3..4,j=3..4): A(i,j) = A(i,j) - A(i,2)*A(2,j)
- only the interchange-step has an effect:
7 7 0 0
0 4 8 2
1 0 3 0
0 0 6 10
step/row 3:
- pivot is A(4,3)=7, interchange rows 3 and 4; LOWER BANDWIDTH INCREASES again
- elimination results in:
7 7 0 0
0 4 8 2
0 0 6 10
1 0 0.5 -5
What is the worst-case running-time complexity of the factorization running on a n-by-n-matrix? (sorry! index computations for band storage and calls to subroutines makes the code a bit hard to read)
- O( n**2 * bandwidth**2 ) ???
- O( n * bandwidth**2 ) ???
thanks a lot!