View source on GitHub
|
Library of popular matrix preconditioners.
Given a matrix M, a preconditioner P of M is an easy to compute approximation of M with the following properties:
1) Pv and P^(-1)v are easy to compute, preferably in time closer to O(n) than O(n^2),
2) det P is easy to compute, and 3) one of M P^(-1), P^(-1) M, or A^(-1) M B^(-1) (with P = A B) is closer to the identity than M is. The specific distance metric we are most often interested in is condition number, and the three options are referred to as "right", "left" or "split" preconditioning respectively.
For more details, see chapter 9 of "Iterative Methods for Sparse Linear Systems", available online at https://www-users.cse.umn.edu/~saad/IterMethBook_2ndEd.pdf
The preconditioners here are intended to be used to improve the convergence of the log det and yt_inv_y operations needed by Gaussian Processes. The preconditioner class you will want to use will depend on the GP kernel type. https://arxiv.org/pdf/2107.00243.pdf suggests that partial Cholesky or QFF work well for RBF kernels, and that RFF or truncated SVD might be good when nothing is known about the kernel structure.
Modules
linalg module: Linear algebra routines to use for preconditioners.
linear_operator_sum module: Expresses a sum of operators.
tfp_math module: Functions for common linear algebra operations.
Classes
class DiagonalPreconditioner: The best diagonal preconditioner; aka the Jacobi preconditioner.
class DiagonalSplitPreconditioner: The split conditioner which pre and post multiplies by a diagonal.
class IdentityPreconditioner: The do-nothing preconditioner.
class LowRankPlusScalingPreconditioner: Turns M ~ a * I + A A^t for low rank A into a preconditioner.
class LowRankPreconditioner: Turns M ~ A A^t for low rank A into a preconditioner.
class LowRankSplitPreconditioner: Turns M ~ A A^t for low rank A into a split preconditioner.
class PartialCholeskyPlusScalingPreconditioner: https://en.wikipedia.org/wiki/Incomplete_Cholesky_factorization .
class PartialCholeskyPreconditioner: https://en.wikipedia.org/wiki/Incomplete_Cholesky_factorization .
class PartialCholeskySplitPreconditioner: https://en.wikipedia.org/wiki/Incomplete_Cholesky_factorization .
class PartialLanczosPlusScalingPreconditioner: https://www.sciencedirect.com/science/article/pii/S0307904X13002382 .
class PartialLanczosPreconditioner: https://www.sciencedirect.com/science/article/pii/S0307904X13002382 .
class PartialLanczosSplitPreconditioner: https://www.sciencedirect.com/science/article/pii/S0307904X13002382 .
class PartialPivotedCholeskyPlusScalingPreconditioner: https://en.wikipedia.org/wiki/Incomplete_Cholesky_factorization .
class Preconditioner: Base class for preconditioners.
class RankOnePreconditioner: Preconditioner based on M ~ v v^t using M's largest eigenvector v.
class RankOneSplitPreconditioner: Split preconditioner based on M ~ v v^t using M's largest eigenvector v.
class SplitPreconditioner: Base class for symmetric split preconditioners.
class TruncatedRandomizedSvdPlusScalingPreconditioner: https://www.math.kent.edu/~reichel/publications/tsvd.pdf .
class TruncatedRandomizedSvdPreconditioner: https://www.math.kent.edu/~reichel/publications/tsvd.pdf .
class TruncatedSvdPlusScalingPreconditioner: https://www.math.kent.edu/~reichel/publications/tsvd.pdf .
class TruncatedSvdPreconditioner: https://www.math.kent.edu/~reichel/publications/tsvd.pdf .
class TruncatedSvdSplitPreconditioner: https://www.math.kent.edu/~reichel/publications/tsvd.pdf .
Functions
get_preconditioner(...): Return the preconditioner of the given type for the given matrix.
resolve_preconditioner(...): Return the resolved preconditioner_name.