Determinante de tridiagonal simétrica matrices

Question

Dado un $n\times n$ matriz tridiagonal

$$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)$$

es posible calcular el determinante de manera más eficiente que el uso de la recurrencia de la relación?

---

En otras palabras, podemos escribir una función que, en teoría, realiza más rápido que el siguiente código (salvo lenguaje de programación de optimizaciones específicas):

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

Answer 1

Si usted está preguntando si alguno de estos determinantes pueden ser resueltos/calculado por un sub-algoritmo de tiempo lineal, la respuesta es obviamente no, porque el $a_i$'s y $d_i$'s pueden tener valores diferentes y por lo tanto es necesario leer cada uno de ellos al menos una vez (y uso el valor leído en alguna operación), así que le da $2n$ (menos algunos pequeños constante, que yo no puede ser molestado en calcular) un límite inferior para la simétrica y $3n$ para el general de la matriz tridiagonal determinante. Asintóticamente, ambos se $\Omega(n)$ del curso.

Caché-localidad retoques, como representación de la [dispersas] matriz por un [no dispersa] matriz de mejorar el rendimiento en la práctica de algunos tamaños de problemas, pero creo que un código de optimización de discusión es bastante off-topic en las matemáticas.SE.

Sin embargo, si los valores son conocidos por ser todos iguales, entonces usted puede tener una constante de tiempo, de forma cerrada de la fórmula, por ejemplo, la respuesta es el número de Fibonacci si $a_i=-1$$c_i=d_i=1$. Hay varios trabajos acerca de tales determinantes; he aquí un ejemplo de uno. Una constante de tiempo de tiempo de algoritmo para tales cerrado fórmulas supone que el resultado es lo suficientemente pequeño para caber en un registro, de lo contrario si usted necesita de cálculo de precisión arbitraria, entonces ya no es adecuado para considerar la constante de tiempo.