1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
lu_int ;
/*
Purpose:
Make one pass over the columns of a rectangular (ncol >= nrow) matrix and
pivot each nonbasic column into the basis when it increases the volume (i.e.
the absolute value of the determinant) of the basis matrix. This is one main
loop of the "maximum volume" algorithm described in [1,2].
[1] C. T. Pan, "On the existence and computation of rank-revealing LU
factorizations". Linear Algebra Appl., 316(1-3), pp. 199-222, 2000
[2] S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov,
N. L. Zamarashkin, "How to find a good submatrix". In "Matrix methods:
theory, algorithms and applications", pp. 247-256. World Sci. Publ.,
Hackensack, NJ, 2010.
Return:
BASICLU_ERROR_invalid_argument when volumetol is less than 1.0.
BASICLU_ERROR_out_of_memory when memory allocation in this function failed.
The return code from a basiclu_obj_* function called when not BASICLU_OK.
(Note that BASICLU_WARNING_singular_matrix means that the algorithm failed.)
BASICLU_OK otherwise.
Arguments:
struct basiclu_object *obj
Pointer to an initialized BASICLU object. The dimension of the object
specifies the number of rows of the matrix.
lu_int ncol
const lu_int Ap[ncol+1]
const lu_int Ai[]
const double Ax[]
Matrix A in compressed sparse column format. Column j contains elements
Ai[Ap[j] .. Ap[j+1]-1], Ax[Ap[j] .. Ap[j+1]-1].
The columns must not contain duplicate row indices. The row indices per
column need not be sorted.
lu_int basis[nrow]
On entry holds the column indices of A that form the initial basis. On
return holds the updated basis. A basis defines a square nonsingular
submatrix of A. If the initial basis is (numerically) singular, then the
initial LU factorization will fail and BASICLU_WARNING_singular_matrix
is returned.
lu_int isbasic[ncol]
This array must be consistent with basis[] on entry, and is consistent
on return. isbasic[j] must be nonzero iff column j appears in the basis.
double volumetol
A column is pivoted into the basis when it increases the absolute value
of the determinant of the basis matrix by more than a factor volumetol.
This parameter must be >= 1.0. In pratcice typical values are 2.0, 10.0
or even 100.0. The closer the tolerances to 1.0, the more basis changes
will usually be necessary to find a maximum volume basis for this
tolerance (using repeated calls to basiclu_obj_maxvolume(), see below).
lu_int *p_nupdate
On return *p_nupdate holds the number of basis updates performed. When
this is zero and BASICLU_OK is returned, then the volume of the initial
basis is locally (within one basis change) maximum up to a factor
volumetol. To find such a basis, basiclu_obj_maxvolume() must be called
repeatedly starting from an arbitrary basis until *p_nupdate is zero.
This will happen eventually because each basis update strictly increases
the volume of the basis matrix. Hence a basis cannot repeat.
p_nupdate can be NULL, in which case it is not accessed. This is not an
error condition. The number of updates performed can be obtained as the
increment to obj->xstore[BASICLU_NUPDATE_TOTAL] caused by the call to
basiclu_obj_maxvolume().
*/