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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr>
//
// Eigen is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// Alternatively, you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; either version 2 of
// the License, or (at your option) any later version.
//
// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License and a copy of the GNU General Public License along with
// Eigen. If not, see <http://www.gnu.org/licenses/>.
/*
* NOTE: This file is the modified version of xcolumn_bmod.c file in SuperLU
* -- SuperLU routine (version 3.0) --
* Univ. of California Berkeley, Xerox Palo Alto Research Center,
* and Lawrence Berkeley National Lab.
* October 15, 2003
*
* Copyright (c) 1994 by Xerox Corporation. All rights reserved.
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
* EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
*
* Permission is hereby granted to use or copy this program for any
* purpose, provided the above notices are retained on all copies.
* Permission to modify the code and to distribute modified code is
* granted, provided the above notices are retained, and a notice that
* the code was modified is included with the above copyright notice.
*/
#ifndef SPARSELU_COLUMN_BMOD_H
#define SPARSELU_COLUMN_BMOD_H
/**
* \brief Performs numeric block updates (sup-col) in topological order
*
* \param jcol current column to update
* \param nseg Number of segments in the U part
* \param dense Store the full representation of the column
* \param tempv working array
* \param segrep segment representative ...
* \param repfnz ??? First nonzero column in each row ??? ...
* \param fpanelc First column in the current panel
* \param glu Global LU data.
* \return 0 - successful return
* > 0 - number of bytes allocated when run out of space
*
*/
template <typename IndexVector, typename ScalarVector, typename BlockIndexVector, typename BlockScalarVector>
int LU_column_bmod(const int jcol, const int nseg, BlockScalarVector& dense, ScalarVector& tempv, BlockIndexVector& segrep, BlockIndexVector& repfnz, int fpanelc, LU_GlobalLU_t<IndexVector, ScalarVector>& glu)
{
typedef typename IndexVector::Scalar Index;
typedef typename ScalarVector::Scalar Scalar;
int jsupno, k, ksub, krep, ksupno;
int lptr, nrow, isub, i, irow, nextlu, new_next, ufirst;
int fsupc, nsupc, nsupr, luptr, kfnz, no_zeros;
/* krep = representative of current k-th supernode
* fsupc = first supernodal column
* nsupc = number of columns in a supernode
* nsupr = number of rows in a supernode
* luptr = location of supernodal LU-block in storage
* kfnz = first nonz in the k-th supernodal segment
* no_zeros = no lf leading zeros in a supernodal U-segment
*/
IndexVector& xsup = glu.xsup;
IndexVector& supno = glu.supno;
IndexVector& lsub = glu.lsub;
IndexVector& xlsub = glu.xlsub;
IndexVector& xlusup = glu.xlusup;
ScalarVector& lusup = glu.lusup;
Index& nzlumax = glu.nzlumax;
jsupno = supno(jcol);
// For each nonzero supernode segment of U[*,j] in topological order
k = nseg - 1;
int d_fsupc; // distance between the first column of the current panel and the
// first column of the current snode
int fst_col; // First column within small LU update
int segsize;
for (ksub = 0; ksub < nseg; ksub++)
{
krep = segrep(k); k--;
ksupno = supno(krep);
if (jsupno != ksupno )
{
// outside the rectangular supernode
fsupc = xsup(ksupno);
fst_col = std::max(fsupc, fpanelc);
// Distance from the current supernode to the current panel;
// d_fsupc = 0 if fsupc > fpanelc
d_fsupc = fst_col - fsupc;
luptr = xlusup(fst_col) + d_fsupc;
lptr = xlsub(fsupc) + d_fsupc;
kfnz = repfnz(krep);
kfnz = std::max(kfnz, fpanelc);
segsize = krep - kfnz + 1;
nsupc = krep - fst_col + 1;
nsupr = xlsub(fsupc+1) - xlsub(fsupc);
nrow = nsupr - d_fsupc - nsupc;
// NOTE Unlike the original implementation in SuperLU, the only feature
// available here is a sup-col update.
// Perform a triangular solver and block update,
// then scatter the result of sup-col update to dense
no_zeros = kfnz - fst_col;
// First, copy U[*,j] segment from dense(*) to tempv(*)
isub = lptr + no_zeros;
for (i = 0; i < segsize; i++)
{
irow = lsub(isub);
tempv(i) = dense(irow);
++isub;
}
// Dense triangular solve -- start effective triangle
luptr += nsupr * no_zeros + no_zeros;
// Form Eigen matrix and vector
// std::cout<< "jcol " << jcol << " rows " << segsize << std::endl;
Map<Matrix<Scalar,Dynamic,Dynamic>, 0, OuterStride<> > A( &(lusup.data()[luptr]), segsize, segsize, OuterStride<>(nsupr) );
VectorBlock<ScalarVector> u(tempv, 0, segsize);
u = A.template triangularView<Lower>().solve(u);
// Dense matrix-vector product y <-- A*x
luptr += segsize;
new (&A) Map<Matrix<Scalar,Dynamic, Dynamic>, 0, OuterStride<> > ( &(lusup.data()[luptr]), nrow, segsize, OuterStride<>(nsupr) );
VectorBlock<ScalarVector> l(tempv, segsize, nrow);
l= A * u;
// Scatter tempv[] into SPA dense[] as a temporary storage
isub = lptr + no_zeros;
for (i = 0; i < segsize; i++)
{
irow = lsub(isub);
dense(irow) = tempv(i);
tempv(i) = Scalar(0.0);
++isub;
}
// Scatter l into SPA dense[]
for (i = 0; i < nrow; i++)
{
irow = lsub(isub);
dense(irow) -= l(i);
l(i) = Scalar(0.0);
++isub;
}
} // end if jsupno
} // end for each segment
// Process the supernodal portion of L\U[*,j]
nextlu = xlusup(jcol);
fsupc = xsup(jsupno);
// copy the SPA dense into L\U[*,j]
int mem;
new_next = nextlu + xlsub(fsupc + 1) - xlsub(fsupc);
while (new_next > nzlumax )
{
mem = LUMemXpand<ScalarVector>(glu.lusup, nzlumax, nextlu, LUSUP, glu.num_expansions);
if (mem) return mem;
}
for (isub = xlsub(fsupc); isub < xlsub(fsupc+1); isub++)
{
irow = lsub(isub);
lusup(nextlu) = dense(irow);
dense(irow) = Scalar(0.0);
++nextlu;
}
xlusup(jcol + 1) = nextlu; // close L\U(*,jcol);
/* For more updates within the panel (also within the current supernode),
* should start from the first column of the panel, or the first column
* of the supernode, whichever is bigger. There are two cases:
* 1) fsupc < fpanelc, then fst_col <-- fpanelc
* 2) fsupc >= fpanelc, then fst_col <-- fsupc
*/
fst_col = std::max(fsupc, fpanelc);
if (fst_col < jcol)
{
// Distance between the current supernode and the current panel
// d_fsupc = 0 if fsupc >= fpanelc
d_fsupc = fst_col - fsupc;
lptr = xlsub(fsupc) + d_fsupc;
luptr = xlusup(fst_col) + d_fsupc;
nsupr = xlsub(fsupc+1) - xlsub(fsupc); // leading dimension
nsupc = jcol - fst_col; // excluding jcol
nrow = nsupr - d_fsupc - nsupc;
// points to the beginning of jcol in snode L\U(jsupno)
ufirst = xlusup(jcol) + d_fsupc;
Map<Matrix<Scalar,Dynamic,Dynamic>, 0, OuterStride<> > A( &(lusup.data()[luptr]), nsupc, nsupc, OuterStride<>(nsupr) );
VectorBlock<ScalarVector> u(lusup, ufirst, nsupc);
u = A.template triangularView<Lower>().solve(u);
new (&A) Map<Matrix<Scalar,Dynamic,Dynamic>, 0, OuterStride<> > ( &(lusup.data()[luptr+nsupc]), nrow, nsupc, OuterStride<>(nsupr) );
VectorBlock<ScalarVector> l(lusup, ufirst+nsupc, nrow);
l = l - A * u;
} // End if fst_col
return 0;
}
#endif
|
