Determinant of symmetric tridiagonal matrices

5.1k Views Asked by At

Given an $n\times n$ tridiagonal matrix

$$A =\left(\begin{array}{ccccccc} d_1&a_1\\c_2&d_2&a_2\\&c_3&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&c_{n-1}&d_{n-1}&a_{n-1}\\&&&&&c_n&d_n \end{array}\right)$$

and

$$f_i =\left|\begin{array}{ccccccc} d_1&a_1\\c_2&d_2&a_2\\&c_3&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&c_{i-1}&d_{i-1}&a_{i-1}\\&&&&&c_i&d_i \end{array}\right|$$

then it is true that the determinants $f_i$ satisfy a three-term recurrence:

$$f_i = d_if_{i-1} - c_ia_{i-1}f_{i-2}$$ for $$f_0=1\text{ and }f_{-1}=0$$

If we are given a symmetric tridiagonal matrix

$$A =\left(\begin{array}{ccccccc} d_1&a_1\\a_1&d_2&a_2\\&a_2&d_3&a_3\\&&&\ddots\\&&&&\ddots\\&&&&a_{n-2}&d_{n-1}&a_{n-1}\\&&&&&a_{n-1}&d_n \end{array}\right)$$

is it possible to calculate the determinant more efficiently than using the recurrence relation?


In other words, can we write a function that theoretically performs quicker than the following code (barring any language/programming-specific optimizations):

double det(double* d, int count, double* a) {
  double f0 = 1;
  double f1 = d[0];
  double ftemp;     

  for (int i = 1; i < count; i++) {
    ftemp = f1;
    f1 = d[i]*f1 - a[i-1]*a[i-1]*f0;
    f0 = ftemp;
  }
  return f1;
}