[Math] Determinant of symmetric tridiagonal matrices

determinantlinear algebramatricessymmetric matricestridiagonal-matrices

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;
}

Best Answer

If you're asking if either of these determinants can be solved/calculated by a sub-linear time algorithm, the answer is obviously no because the $a_i$'s and $d_i$'s can all have different values and thus you need to read each of them at least once (and use the value read in some operation), so that gives $2n$ (minus some small constant, which I can't be bothered to calculate) a lower bound for the symmetric one and $3n$ for the general tridiagonal matrix determinant. Asymptotically, both are $\Omega(n)$ of course.

Cache-locality tweaks, like representing the [sparse] matrix by a [non-sparse] array would improve performance in practice for some sizes of problems, but I think such a code tuning discussion is rather off-topic on math.SE.

However if the values are known to be all the same, then you can have a constant-time, closed-form formula, e.g. the answer is the Fibonacci number if $a_i=-1$ and $c_i=d_i=1$. There are several papers about such determinants; here's an example one. A constant-time time algorithm for such closed formulas assumes the result is small enough to fit in a register, otherwise if you need arbitrary-precision arithmetic, then it's no longer proper to consider them constant time.

Related Question