Function eigen_symmetric_tridiagonal 

pub fn eigen_symmetric_tridiagonal(
    d_in: Vec<f64>,
    e_in: Vec<f64>,
) -> (Vec<f64>, Vec<f64>)

Symmetric Tridiagonal Eigenvalue Solver

This module solves the eigenvalue problem $Ax = \lambda x$ for a real symmetric tridiagonal matrix $A$.

Mathematical Formulation

A symmetric tridiagonal matrix $A$ has the form:

$$ A = \begin{pmatrix} d_1 & e_1 & 0 & \cdots & 0 \ e_1 & d_2 & e_2 & \cdots & 0 \ 0 & e_2 & d_3 & \ddots & \vdots \ \vdots & \vdots & \ddots & \ddots & e_{n-1} \ 0 & 0 & \cdots & e_{n-1} & d_n \end{pmatrix} $$

where $d_i$ are the diagonal elements and $e_i$ are the off-diagonal elements.

Because $A$ is real symmetric, every eigenvalue is real and there is an orthonormal basis of eigenvectors. The spectral decomposition is $A = Z \Lambda Z^T$, where $Z$ is orthogonal ($Z^T Z = I$) and $\Lambda = \mathrm{diag}(\lambda_1, \ldots, \lambda_n)$.

Algorithm

The solver wraps LAPACK’s DSTEV, which uses the implicit QL or QR algorithm specialized to symmetric tridiagonal matrices. The method iteratively applies orthogonal similarity transformations that preserve both symmetry and tridiagonality while driving the off-diagonal entries toward zero; the diagonal entries then converge to the eigenvalues.

• Shift: At each implicit QL step a shift is chosen from the trailing $2 \times 2$ block to accelerate convergence; the LAPACK driver does not expose this choice to the caller.
• Transformation: A sequence of Givens rotations is applied on both sides, $A’ = Q^T A Q$, keeping the result symmetric tridiagonal.
• Convergence: The process repeats until the off-diagonal entries are negligible and the diagonal entries are the eigenvalues, returned in ascending order.

The eigenvectors are accumulated by composing the rotations into the matrix $Z = Q_1 Q_2 \cdots Q_k$.

Implementation Details

• Input: Diagonal vector $d$ (length $n$) and off-diagonal vector $e$ (length $n-1$), where $e_i$ is the element at position $(i, i+1)$. An input $e$ of length $n$ is accepted and truncated to its first $n-1$ entries.
• Output: Eigenvalues in ascending order and the corresponding eigenvectors.
• Eigenvector layout: The eigenvectors are returned in a single flattened column-major buffer of length $n^2$, where index i + j * n holds the $i$-th component of the $j$-th eigenvector, that is row $i$, column $j$ of $Z$.

Validation targets are the known closed forms in solver/tests/infra/linalg.rs: the $2 \times 2$ tridiagonal Toeplitz matrix with eigenvalues $1$ and $3$, the $3 \times 3$ case with eigenvalues $2 - \sqrt 2$, $2$, $2 + \sqrt 2$, and the matrix with integer eigenvalues $0$, $1$, $3$.

Arguments

• d_in - The diagonal elements of the matrix.
• e_in - The off-diagonal elements of the matrix. e[i] is the element at (i, i+1).

Returns

A tuple containing:

• A vector of eigenvalues.
• A flattened vector of eigenvectors (column-major). The element at row i and column j is at index i + j * n.

Examples

use solver::linalg::eigen::eigen_symmetric_tridiagonal;

// Matrix:
// [ 2 -1 ]
// [-1  2 ]
// Eigenvalues should be 1 and 3.

let d = vec![2.0, 2.0];
let e = vec![-1.0]; // Off-diagonal

let (evals, evecs) = eigen_symmetric_tridiagonal(d, e);

assert!((evals[0] - 1.0).abs() < 1e-6);
assert!((evals[1] - 3.0).abs() < 1e-6);