You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Austin Gill 8c93297728 Remove TODO list 1 year ago
papers Remove TODO list 1 year ago
solver Completely strip out HSS approximations to profile 1 year ago
tests Clean up unit tests 1 year ago
tools Add blurb in README about repo layout 1 year ago
.gitignore add vs code workspace to gitignore 1 year ago
README.md Add blurb in README about repo layout 1 year ago
full_test_counter.m Add blurb in README about repo layout 1 year ago

README.md

Research

The Git repository for my mathematics senior research.


Idea

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.

Repository Layout

  • The main entry point for running tests on our EigenCounter implementation is the m-file full_test_counter.m.
  • There are a number of tools defined in tools/. The most notable of which is tools/TestMatrix.m which generates a Cauchy-like rank-structured matrix.
  • There are a few unit tests in tests/. Unfortunately I have not kept up with them as much as I should have. Run the unit tests with
  >> cd tests
  >> runtests
  • The research paper, mid-year progress report, and colloquium presentation LaTeX source code is found in papers/, along with Makefiles to build them (on a Linux machine).
  • The actual source code for the eigensolver is found in 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));