Skip to content

divide-and-conquer eigenvalues algorithm for symmetric tridiagonal matrix, designed by Cuppen

License

Notifications You must be signed in to change notification settings

masyagin1998/divide-and-conquer-eigenvalues

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

30 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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:

In russian:

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:

About

divide-and-conquer eigenvalues algorithm for symmetric tridiagonal matrix, designed by Cuppen

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published