-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
225 lines (181 loc) · 10.7 KB
/
README
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
███████╗ ██╗ ██╗ ███████╗ ██╗
██╔════╝ ██║ ██║ ██╔════╝ ██║
█████╗ ██║ ██║ ███████╗ ██║
██╔══╝ ╚██╗ ██╔╝ ╚════██║ ██║
███████╗ ██╗ ╚████╔╝ ██╗ ███████║ ██╗ ███████╗
╚══════╝ ╚═╝ ╚═══╝ ╚═╝ ╚══════╝ ╚═╝ ╚══════╝
Version 1.0 Latest changes made on: Thu Feb 2 15:35:51 CST 2017
-----------------------------------------------------------------------
EVSL: ChebLanTR, ChebLanNR, ChebSI, RatLanTr, and RatLanNr
Polynomial and Rational Filtered Lanczos and subspace
iteration algorithms For Symmetric Eigenvalue problems
-----------------------------------------------------------------------
Welcome to EVSL. EVSL is a C library for computing the eigenvalues of
a symmetric matrix that are located in a given interval. This first
release includes the routines listed above and does not yet offer full
parallel implementations (trivial openMP test programs are available
in among the test drivers). EVSL also provides tools for spectrum
slicing, i.e., the technique of subdividing a given interval into p
smaller subintervals and computing the eigenvalues in each subinterval
independently. EVSL implements a polynomial filtered Lanczos (thick
restart, no restart) a rational filtered Lanczos (thick restart, no
restart), and a polynomial filtered subspace iteration.
For questions/feedback send e-mail to Yousef Saad [[email protected]]
-----------------------------------------------------------------------
-----------------------------------------------------------------------
Description of contents:
=======================
FILES:
INC/
evsl.h : user-level function prototypes and constant definitions
blaslapack.h : C API for BLAS/LAPACK functions used in evsl
def.h : miscellaneous macros
struct.h : miscellaneous structs used in evsl
internal_proto.h : internal function prototypes for SRC/
SRC/
chelanNr.c : Polynomial Filtered no-restart Lanczos
chelanTr.c : Polynomial Filtered thick restart Lanczos
chebpoly.c : Computing and applying polynomial filters
chebsi.c : Polynomial Filtered Subspace iteration
dumps.c : Miscellaneous functions for I/O and for debugging
evsl.c : Set global variable evslData
lanbounds.c : Lanczos alg. to give a bound of spectrum
mactime.c : Timer for mac os
misc_la.c : Miscellaneous linear algebra functions
ratfilter.c : Computing and applying rational filters
ratlanNr.c : Rational Filtered no-restart Lanczos
ratlanTr.c : Rational Filtered thick restart Lanczos
spmat.c : Sparse matrix routines
spslicer.c : Spectrum slicing
suitesparse.c : Interface to SuiteSparse
timing.c : Timer
vect.c : Vector operations
liblancheb.a : library
TESTS_Gen/ and TESTS_Lap/ :
directories containing test drivers for
simple model Laplacean matrices (TESTS_Lap) or general matrices in
sparse format read from a file (TESTS_Gen)
See below and 00README files therein for further information
-----------------------------------------------------------------------
INSTALLATION
-----------------------------------------------------------------------
Library:
The users only need to modify the file makefile.in
[see makefile.in.example for samples of files makefile.in
that are given for mac-os and for Linux].
1. cp makefile.in_Linux/MacOS.example makefile.in.
2. modify makefile.in
[provide BLAS/LAPACK path, and optionally SuiteSparse path]
3. make clean; make
make in the directory SRC will create the library liblancheb.a
Test programs:
In directories TESTS_Lap and TESTS_Gen you will find makefiles to
run sample drivers that test a few different situations.
TESTS_Lap/ -- generate Laplacean matrices and compute eigenvalues in
given intervals. You will find 5 drivers
LapPLanN.c --> poly. filtering non-restarted Lanczos
LapPLanR.c --> poly. filtering thick-restart Lanczos
LapPSI.c --> poly. filtering subspace iteration
LapRLanN.c --> rational filtering non-restart Lanczos
LapRLanR.c --> rational filtering thick-restart Lanczos
lapl.c --> functions to set up a laplacean matrix and also to
compute the exact eigenvalues of Laplacians
see details in the 00README file in the directory TESTS_Lap/
TESTS_Gen/ -- read a matrix from file and compute eigenvalues in
given intervals. Here you will find 6 drivers
GenPLanN.c --> poly. filtering non-restarted Lanczos
GenPLanR.c --> poly. filtering thick-restart Lanczos
GenPSI.c --> poly. filtering subspace iteration
GenPLanR_omp.c --> poly. filtering thick-restart Lanczos with openMP
GenRLanN.c --> rational filtering non-restart Lanczos
GenRLanR.c --> rational filtering thick-restart Lanczos
see details in the 00README file in the directory TESTS_Gen/
-----------------------------------------------------------------------
RATIONAL FILTERING
-----------------------------------------------------------------------
Rational filtering requires solving linear systems (where the
coefficient matrix is the original matrix shifted by a *complex*
shift). A linear solver routine must be provided. By default EVSL
uses UMFPACK, a sparse direct solver package by T. Davis. (version
4.5.3 has been tested)
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
NOTE: SuiteSparse is NOT distributed with EVSL, and is Copyrighted (c)
by Timothy Davis. Please refer to that package for its License.
[http://faculty.cse.tamu.edu/davis/suitesparse.html]
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
After having computed the rational filter by "find_ratf(intv,
&rat)", users can call "set_ratf_solfunc(&rat, &Acsr, NULL, NULL)"
to tell EVSL to use UMFPACK to factorize the shifted matrices and
solve the linear systems. The factors will be saved in struct rat.
EVSL can also take user-specified solvers. To do this, call
"set_ratf_solfunc(&rat, &Acsr, func, data)" to pass the solver
functions and the associated data for each pole. "func" is an array
of function pointers of length num of poles, i.e., rat->num. So,
func[i] is the function to solve the systems with pole i, the
coefficient matrix of which is $A - s_i I$, where s_i = rat->zk[i]
is the complex shift. "data" is an array of (void*) of the same
length, where data[i] is the data needed by func[i].
All "func" must be of the following prototype
void linsolFunc(int n, double *br, double *bz, double *xr,
double *xz, void *data);
where n is the size of the system, br, bz are the right-hand
side (real and imaginary parts of complex vector), xr, xz will
be the solution (complex vector), and "data" contains all the
data needed for the solver.
Once "set_ratf_solfunc" is done, rational filtering Lanczos methods
should be ready to use.
-----------------------------------------------------------------------
LINKING WITH UMFPACK (SuiteSparse 4.5.3)
-----------------------------------------------------------------------
The makefiles in TESTS_Lap and TEST_Gen, include paths to
SuiteSparse 4.5.3. UMFPACK requires AMD, CHOLMOD, COLAMD, CCOLAMD
and CAMD, and optionally METIS 5.1.0. Compile each of these
packages to have the library file in the Lib directory. If
SuiteSparse is configured with METIS, give the path to METIS (v
5.1.0) as well (to make libmetis.a, type `make config' in
metis-5.1.0/ and then `make') Please refer to SuiteSparse and METIS
for installation details.
-----------------------------------------------------------------------
MATRIX-FREE SOLVERS
-----------------------------------------------------------------------
All the iterative solvers in EVSL can be used in matrix-free
ways. Users need only to provide the matrix-vector product function
of the following prototype:
void Matvec(double *x, double *y, void *data);
where y = A * x and data is the pointer to the associated data to
perform the matvec. The (void *) argument is to provide a uniform
interface to all user-specific functions. For a particular Matvec
function, one can pack all data needed by this function into a struct
and pass the pointer of this struct to EVSL (after cast it to (void
*)). This function needs to be passed to EVSL as well, so EVSL can
call this function to perform all matvecs. Note that when the
user-input matvec function is set, the CSR matrix will not be
referenced even if it is provided (so it is safe to give NULL for the
matrix input in this case).
In TEST_LAP, an example of matvec functions for 2D/3D Laplacian
matrices is provided, where the matrix is not explicitly formed but
5pt/7pt stencil is used instead. In this example, a struct for matvec
is first defined:
typedef struct _lapmv_t {
int nx, ny, nz;
double *stencil;
} lapmv_t;
and the matvec function is implemented
void Lap2D3DMatvec(double *x, double *y, void *data) {
lapmv_t *lapmv = (lapmv_t *) data;
int nx = lapmv->nx;
int ny = lapmv->ny;
int nz = lapmv->nz;
double *stencil = lapmv->stencil;
...
}
in which the pointer is first casted and all the data is
unpacked. Once these are ready, they can be passed to EVSL by calling
SetMatvecFunc(n, &Lap2D3DMatvec, (void*) &lapmv);
where the first input is the size of the "matrix", the second input is
the function pointer and the third one is the data pointer. Once
"SetMatvecFunc" is called, EVSL will use the registered matvec
function to perform all matvecs.
Users should first create a function wrapper of the above type for an
external matvec routine. Then, following the steps in the example, it
will be straightforward to use it in EVSL.