jacobi_eig.hpp File Reference

Full symmetric eigendecomposition via cyclic Jacobi sweeps. More...

#include "core/matrix.hpp"
#include "core/vector.hpp"
#include "core/policy.hpp"
#include <cmath>
#include <algorithm>
#include <stdexcept>

Go to the source code of this file.

Classes
struct	num::EigenResult
	Full eigendecomposition result: A = V * diag(values) * V^T. More...

Namespaces
namespace	num

Functions
EigenResult	num::eig_sym (const Matrix &A, real tol=1e-12, idx max_sweeps=100, Backend backend=Backend::seq)
	Full eigendecomposition of a real symmetric matrix.

Detailed Description

Full symmetric eigendecomposition via cyclic Jacobi sweeps.

Computes ALL eigenvalues and eigenvectors of a real symmetric matrix.

Algorithm – cyclic Jacobi: Repeatedly apply plane (Givens) rotations in the (p,q) plane to zero the off-diagonal element A[p,q]. Each rotation is a similarity transform so eigenvalues are preserved. Convergence is quadratic: after each full sweep the sum of squared off-diagonal elements decreases by at least a constant factor.

Why Jacobi instead of the implicit QR algorithm? Jacobi is conceptually simpler and each rotation is the exact same 2x2 eigendecomposition students encounter first. For dense n < 1000 the performance is acceptable. LAPACK uses the Francis QR algorithm (dsyev) which is O(n^2) per iteration vs O(n^2) per sweep here, but harder to explain.

Complexity: O(n^2) per sweep, O(n) sweeps typical -> O(n^3) total.

Definition in file jacobi_eig.hpp.