banfac Subroutine

BANFAC returns in W the LU-factorization, without pivoting, of 
the banded matrix A of order NROW with (NBANDL+1+NBANDU) bands 
or diagonals in the work array W.

Gauss elimination without pivoting is used.  The routine is 
intended for use with matrices A which do not require row 
interchanges during factorization, especially for the totally 
positive matrices which occur in spline calculations.

The matrix storage mode used is the same one used by LINPACK 
and LAPACK, and results in efficient innermost loops.

Explicitly, A has

  NBANDL bands below the diagonal
  1     main diagonal
  NBANDU bands above the diagonal

and thus, with MIDDLE=NBANDU+1,
A(I+J,J) is in W(I+MIDDLE,J) for I=-NBANDU,...,NBANDL, J=1,...,NROW.

For example, the interesting entries of a banded matrix
matrix of order 9, with NBANDL=1, NBANDU=2:

  11 12 13  0  0  0  0  0  0
  21 22 23 24  0  0  0  0  0
   0 32 33 34 35  0  0  0  0
   0  0 43 44 45 46  0  0  0
   0  0  0 54 55 56 57  0  0
   0  0  0  0 65 66 67 68  0
   0  0  0  0  0 76 77 78 79
   0  0  0  0  0  0 87 88 89
   0  0  0  0  0  0  0 98 99

would appear in the first 1+1+2=4 rows of W as follows:

   0  0 13 24 35 46 57 68 79
   0 12 23 34 45 56 67 78 89
  11 22 33 44 55 66 77 88 99
  21 32 43 54 65 76 87 98  0

All other entries of W not identified in this way with an
entry of A are never referenced.

This routine makes it possible to solve any particular linear system 
A*X=B for X by the call

  call banslv ( w, nroww, nrow, nbandl, nbandu, b )

with the solution X contained in B on return.

If IFLAG=2, then one of NROW-1, NBANDL, NBANDU failed to be nonnegative, 
or else one of the potential pivots was found to be zero 
indicating that A does not have an LU-factorization.  This 
implies that A is singular in case it is totally positive.

14 February 2007

Carl DeBoor

Carl DeBoor,
A Practical Guide to Splines,
Springer, 2001,
ISBN: 0387953663,
LC: QA1.A647.v27.

Input/output, real ( kind = 8 ) W(NROWW,NROW).
On input, W contains the "interesting" part of a banded 
matrix A, with the diagonals or bands of A stored in the
rows of W, while columns of A correspond to columns of W. 
On output, W contains the LU-factorization of A into a unit 
lower triangular matrix L and an upper triangular matrix U 
(both banded) and stored in customary fashion over the 
corresponding entries of A.

Input, integer ( kind = 4 ) NROWW, the row dimension of the work array W.
NROWW must be at least NBANDL+1 + NBANDU.

Input, integer ( kind = 4 ) NROW, the number of rows in A.

Input, integer ( kind = 4 ) NBANDL, the number of bands of A below 
the main diagonal.

Input, integer ( kind = 4 ) NBANDU, the number of bands of A above 
the main diagonal.

Output, integer ( kind = 4 ) IFLAG, error flag.
1, success.
2, failure, the matrix was not factored.