Austin Gill 8c93297728 Remove TODO list | 9 months ago | |
---|---|---|
papers | 9 months ago | |
solver | 11 months ago | |
tests | 10 months ago | |
tools | 9 months ago | |
.gitignore | 1 year ago | |
README.md | 9 months ago | |
full_test_counter.m | 9 months ago |
The Git repository for my mathematics senior research.
Eigenvalues are the zeros of a characteristic polynomial. Polynomials are entire, and their zeros become poles when inverted. Poles are very important in Complex Analysis. In particular, there exist methods of counting the number of poles inside of a given contour using Cauchy's Argument Principle. Perhaps it is possible to apply Complex Analysis and implement an eigensolver.
Unsurprisingly, there are a number of existing eigensolvers using this concept. In particular, this research project will examine the paper A Fast Contour-Integral Eigensolver for non-Hermitian Matrices in an attempt to understand, implement, and hopefully improve the work done by the authors. Here is my abstract in its current form.
We examine a new complex contour integral-based eigensolver algorithm using ideas from functional analysis. This eigensolver algorithm extends previous eigensolvers that typically required some special structure, to an eigensolver that works on a more general class of complex-valued matrices.
The algorithm consists of two stages. First, it searches the complex plane for regions dense with eigenvalues. Second, it combs through those regions to find the eigenvalues using a modified form of the FEAST algorithm.
Due to time constraints we were only able to examine the first stage in detail, and for completeness provide a description for the second stage. Our work was exploratory in nature, which in practice consisted of building and testing a Matlab implementation of the first stage.
EigenCounter
implementation is the m-file full_test_counter.m
.tools/
. The most notable of which is tools/TestMatrix.m
which generates a Cauchy-like rank-structured matrix.tests/
. Unfortunately I have not kept up with them as much as I should have. Run the unit tests with >> cd tests
>> runtests
papers/
, along with Makefiles to build them (on a Linux machine).solver/
and is broken down into logical pieces. This is also where the HSS library below can be found.hss
The solver/hss/
Matlab library is from Dr. Jianlin Xia and company from Purdue University. Example usage seems to be in hss/test.m
of an HSS approximation of a matrix. The functionality seems to be more or less the following:
load A.mat
% HSS metaparameters
n = size(A, 1);
% HSS block row size
r = 16;
tol = 1e-6;
[tr, m] = npart(n, r);
[D, U, R, B, W, V, nflops] = mat2hss(A, tr, m, 'tol', tol);
A1 = hss2mat(D, U, R, B, W, V, tr);
% The following should be a very small number
disp(norm(A - A1) / norm(A));