Chebyshev Polynomials

Overview

This module allows you to compute an arbitrary Chebyshev polynomial of a matrix, based on the supplied coefficients. The Chebyshev polynomials are defined as:

T_0 = I

T_1 = A

T_{i+1} = 2AT_i - T_{i-1}.

Method

We have two implementations available. The first computes the function in the straightforward way. At each step, the next Polynomial is computed, and added to the output matrix.

Unfortunately, this is slow. However, it has the advantage of being low in memory, and potentially this approach could be modified for when you have to compute many different functions of the same matrix (each with different coefficients).

A faster way is based on a divide and conquer method. I'll sketch it out here. Consider a low degree function:

f(A) = a_0T_0 + a_1T_1 + a_2T_2 + a_3T_3

Normally you would have to compute each Chebyshev polynomial, and sum it together. But we can also write this is a divide and conquer fashion, using the relationship:

T_{n+m}(A) = 2T_n(A)T_m - T_{|n-m|}(A)

Now rewrite the above equation:

f(A) = a_0T_0 + a_1T_1 + a_2(2T_2T_0 - T_2) + a_3(2T_2T_1 - T_1)

f(A) = a_0T_0 + (a_1-a_3)T_1 + 2T_2(a_2T_0 + a_3T_1) - a_2T_2

If you do this recursively, you end up only have to compute the powers of 2 T matrices, and then do one multiplication at each level to sum things back together.

How to Cite

I think it is important to cite this paper by Liang.

@article{liang2003improved,
title={Improved Fermi operator expansion methods for fast electronic structure calculations},
author={Liang, WanZhen and Saravanan, Chandra and Shao, Yihan and Baer, Roi and Bell, Alexis T and Head-Gordon, Martin},
journal={The Journal of chemical physics},
volume={119},
number={8},
pages={4117--4125},
year={2003},
publisher={AIP}
}

However, to be honest I found it a little difficult to understand. So instead of using their divide and conquer based on even's and odds, I used the factorization presented above. It's really the same idea, but I think it's much easier to program.