dimforge / dimforge/nalgebra

Tracking of sparsity, low-rank update structure, etc.

Open
#822 0 comments 3 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
4.8k
Forks
565
PR merge metrics
No merged PRs in 30d

Description

Many optimization algorithms ultimately boil down to (repeated) invocation of Newton's method, which involves solving the linear system `∇²f(x) * x = -∇f(x)`. This is fairly efficient until you start dealing with high-dimensional problems (e.g.: 10k - 10M variables), at which point Gaussian elimination becomes expensive (and even materializing the whole matrix can be an issue). However, it turns out that in many cases, there is structure in `∇²f(x)` (the Hessian) that allows solving this linear system much faster than with plain Gaussian elimination.

For example:
- If the matrix is the identity matrix, you don't have to do any work to solve the system.
- If the matrix is a diagonal matrix, you just need to divide by each element along the diagonal.
- If the matrix is tridiagonal, you can solve the system in O(n) time with the Thomas algorithm.
- If the matrix is circulant, you can solve it faster via FFT.
- If the matrix is Toeplitz, it can be solved in O(n²) time with the Levinson algorithm.
- If the matrix is a DFT matrix, then you can just compute the inverse DFT of `-∇f(x)`.
- If the matrix is the sum of a low-rank matrix and an easily-solved matrix, then you can use the [Woodbury matrix identity](https://en.wikipedia.org/wiki/Woodbury_matrix_identity) to compute the solution for the sum.
- If a block of the matrix has structure, the matrix can be solved blockwise (i.e.: if any of the blocks have structure, you can save time).

I think it would be a cutting edge and important feature if nalgebra had support for tracking this information about structure during computations (and eventually, exploiting that information by choosing an appropriate data representation and solution method).

Most competitors in this space instead have heuristics for checking if the given matrix has some structure, and then exploiting it, but these heuristics add overhead and simply cannot detect some structure (e.g.: low-rank update structure, DFT structure).

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.