divide-and-conquer-eigenvalues

This is realization of divide-and-conquer eigenvalues algorithm for symmetric tridiagonal matrix, designed by Cuppen in 1982.

Tech

Algorithm is coded in pure C99. You can compile it with C89 compiler easily, if You change long double to doule, sqrtl and fabsl to sqrt and abs, or declare Your own sqrtl and fabsl (C89 doesn’t have them) and change C version in Makefile.

Installation

divide-and-conquer-eigenvalues requires only C99-compatible compiler and make utility.

$ cd divide-and-conquer-eigenvalues
$ make
$ ./bin/test data/in.mat

Short description

divide-and-conquer-eigenvalues finds for given symmetric tridiagonal matrix T matrices of eigenvectors Q and eigenvalues L, such T = Q * L * Q_t, partitioning large T matrix into two half-sized matrices T1 and T2 (they are also partitioned, so we use divide-and-conquer strategy).

Optimization

You can add thread-pool to this algorithm:

• recursive divide-and-conquer steps can be processed in parallel. You can divide recursive calls to current thread and additional thread;
• secular equation can be solved in parallel too, because its routine doesn’t modify any input matrices;
• matrix inversion step can be simplified (because matrix should be tridiagonal);

Usefull articles

In english:

• Arbenz P. Lecture Notes on Solving Large Scale Eigenvalue Problems
• Arbenz P. - his website with lectures, presentations, etc
• Demmel J. W. Applied Numerical Linear Algebra
• Rutter J. A Serial Implementation of Cuppen’s Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem

In russian:

• Golubkov A. Yu. Lecture notes on computational methods of linear algebra.
• AlgoWiki Divide-and-Conquer

TODOs:

• Change all long long double to complex, to not to fail on some matricies.

Many thanks to:

• Golubkov A. Yu. - BMSTU algebra, Galois theory, Rings theory and NMLA teacher;

Referenced or mentioned by:

• Shrey Dabhi, Manojkumar Parmar. Eigenvector Component Calculation Speedup over NumPy for High-Performance Computing