|
of |
nequ equations in case a is almost block diagonal with all
|
|
blocks having |
| |
ncols columns using no more storage than it takes to
|
|
store the interesting part of |
| |
a . such systems occur in the determ-
ination of the b-spline coefficients of a spline approximation.
|
parameters
|
|
w |
on input, a two-dimensional array of size (nequ,ncols) contain-
ing the interesting part of the almost block diagonal coeffici-
|
|
|
ent matrix | | |
a (see description and example below). the array
|
|
integs |
describes the storage scheme.
|
|
on output, w | | |
contains the upper triangular factor u of the
|
|
lu factorization of a possibly permuted version of | | |
a . in par-
|
|
ticular, the determinant of | | |
a could now be found as
|
|
|
iflag*w(1,1)*w(2,1)* ... * w(nequ,1) | | |
|
|
|
|
|
|
b |
on input, the right side of the linear system, of length nequ.
|
|
|
the contents of | | |
b are changed during execution.
|
|
|
|
nequ |
number of equations in system
ncols block width, i.e., number of columns in each block.
|
|
integs |
integer array, of size (2,nequ), describing the block struct-
|
|
|
ure of |
a .
|
|
|
integs(1,i) = no. of rows in block i | | |
= nrow
integs(2,i) = no. of elimination steps in block i
|
|
|
= overhang over next block | | |
= last
|
|
|
|
|
|
|
|
nbloks |
number of blocks
|
|
d |
work array, to contain row sizes . if storage is scarce, the
|
|
|
array |
x could be used in the calling sequence for d .
|
|
|
|
x |
on output, contains computed solution (if iflag .ne. 0), of
|
|
iflag |
on output, integer
= (-1)**(no.of interchanges during elimination)
|
|
= |
0 if a is singular
|
|
|
------ |
block structure of a ------
|
|
|
|
the interesting part of |
| |
a is taken to consist of nbloks con-
|
|
secutive blocks, with the i-th block made up of |
| |
nrowi = integs(1,i)
|
|
consecutive rows and |
| |
ncols consecutive columns of a , and with
|
|
the first |
| |
lasti = integs(2,i) columns to the left of the next block.
|
|
these blocks are stored consecutively in the workarray |
| |
w .
for example, here is an 11th order matrix and its arrangement in
|
|
the workarray |
| |
w . (the interesting entries of a are indicated by
their row and column index modulo 10.)
|
--- a --- --- w ---
nrow1=3
|
| |
|
11 12 13 14 | | |
11 12 13 14
|
|
21 22 23 24 | | |
21 22 23 24
|
|
31 32 33 34 | | |
nrow2=2 31 32 33 34
|
|
|
|
last1=2 |
| |
43 44 45 46 43 44 45 46
|
|
|
53 54 55 56 | | |
nrow3=3 53 54 55 56
|
|
|
|
last2=3 |
| |
66 67 68 69 66 67 68 69
|
|
|
76 77 78 79 | | |
76 77 78 79
|
|
86 87 88 89 | | |
nrow4=1 86 87 88 89
|
|
|
|
last3=1 |
| |
97 98 99 90 nrow5=2 97 98 99 90
|
|
|
last4=1 | | |
08 09 00 01 08 09 00 01
|
|
|
18 19 10 11 | | |
18 19 10 11
last5=4
|
|
|
|
|
|
for this interpretation of |
| |
a as an almost block diagonal matrix,
|
|
we have |
| |
nbloks = 5 , and the integs array is
|
i= 1 2 3 4 5
k=
|
|
integs(k,i) = |
| |
1 3 2 3 1 2
|
|
-------- |
| |
method --------
gauss elimination with scaled partial pivoting is used, but mult-
|
|
ipliers are |
| |
n o t s a v e d in order to save storage. rather, the
right side is operated on during elimination.
the two parameters
|
|
|
i p v t e q | | |
and l a s t e q
|
|
|
|
are used to keep track of the action. |
| |
ipvteq is the index of the
|
|
variable to be eliminated next, from equations |
| |
ipvteq+1,...,lasteq,
|
|
using equation |
| |
ipvteq (possibly after an interchange) as the pivot
|
|
equation. the entries in the pivot column are |
| |
a l w a y s in column
|
|
1 of |
w . this is accomplished by putting the entries in rows
|
|
ipvteq+1,...,lasteq |
| |
revised by the elimination of the ipvteq-th
|
|
variable one to the left in |
| |
w . in this way, the columns of the
|
|
equations in a given block (as stored in |
| |
w ) will be aligned with
those of the next block at the moment when these next equations be-
come involved in the elimination process.
thus, for the above example, the first elimination steps proceed
as follows.
|
|
*11 12 13 14 |
| |
11 12 13 14 11 12 13 14 11 12 13 14
|
|
*21 22 23 24 |
| |
*22 23 24 22 23 24 22 23 24
|
|
*31 32 33 34 |
| |
*32 33 34 *33 34 33 34
|
|
|
43 44 45 46 | | |
43 44 45 46 *43 44 45 46 *44 45 46 etc.
|
|
53 54 55 56 | | |
53 54 55 56 *53 54 55 56 *54 55 56
|
|
66 67 68 69 | | |
66 67 68 69 66 67 68 69 66 67 68 69
|
|
in all other respects, the procedure is standard, including the
scaled partial pivoting.
|
|
