No Description

Austin Gill 8c93297728 Remove TODO list 8 months ago
papers 8c93297728 Remove TODO list 8 months ago
solver 1a04d1e460 Completely strip out HSS approximations to profile 10 months ago
tests 4d9b0ca903 Clean up unit tests 9 months ago
tools eec6c866d8 Add blurb in README about repo layout 8 months ago
.gitignore 9bacf85887 add vs code workspace to gitignore 11 months ago
README.md eec6c866d8 Add blurb in README about repo layout 8 months ago
full_test_counter.m eec6c866d8 Add blurb in README about repo layout 8 months 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));