6
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ Indeed, use x*x instead of pow(x,2) $\endgroup$ – Algebraic Pavel Nov 21 '13 at 10:21
  • $\begingroup$ @AlgebraicPavel that is true, but I'm talking more algorithmically as opposed to specifically the code I wrote. Regardless, I changed the code to include the improvement :) $\endgroup$ – Alex Brooks Nov 21 '13 at 16:45
  • $\begingroup$ I'd be interested in a bit more general question: How does one efficiently compute the eigenvalues of such matrices? $\endgroup$ – Semiclassical Jul 24 '14 at 15:03
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.