Content deleted Content added
Removed {{Underlinked}} tag |
Citation bot (talk | contribs) Alter: bibcode. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to ISBN13. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with specifically marked weasel-worded phrases from October 2021 | #UCB_Category 19/403 |
||
Line 2:
[[File:Extended_Sparse_Matrix.png|thumb|Extended Sparse Matrix arising from a <math>10 \times 10</math> semi-separable matrix whose semi-separable rank is <math>4</math>.]]
The '''Rybicki–Press algorithm''' is a fast [[algorithm]] for inverting a [[Matrix (mathematics)|matrix]] whose entries are given by <math>A(i,j) = \exp(-a \vert t_i - t_j \vert)</math>, where <math>a \in \mathbb{R}</math><ref name=":2">{{citation
|last1 = Rybicki|first1 = George B.|last2 = Press|first2 = William H.|arxiv = comp-gas/9405004|doi = 10.1103/PhysRevLett.74.1060|journal = Physical Review Letters|title = Class of fast methods for processing Irregularly sampled or otherwise inhomogeneous one-dimensional data|volume = 74|issue = 7|pages = 1060–1063|year = 1995|bibcode = 1995PhRvL..74.1060R|pmid=10058924|s2cid = 17436268}} {{Open access}}</ref> and where the <math>t_i</math> are sorted in order.<ref name=":3" /> The key observation behind the Rybicki-Press observation is that the [[matrix inverse]] of such a matrix is always a [[tridiagonal matrix]] (a matrix with nonzero entries only on the main diagonal and the two adjoining ones), and [[Tridiagonal matrix algorithm|tridiagonal systems of equations]] can be solved efficiently (to be more precise, in linear time).<ref name=":2" /> It is a computational optimization of a general set of statistical methods developed to determine whether two noisy, irregularly sampled data sets are, in fact, dimensionally shifted representations of the same underlying function.<ref>{{Cite journal|title = Interpolation, realization, and reconstruction of noisy, irregularly sampled data|
The method has been extended to the '''Generalized Rybicki-Press algorithm''' for inverting matrices with entries of the form <math>A(i,j) = \sum_{k=1}^p a_k \exp(-\beta_k \vert t_i - t_j \vert)</math>.<ref name=":3">{{Cite journal|last=Ambikasaran|first=Sivaram|date=2015-12-01|title=Generalized Rybicki Press algorithm|journal=Numerical Linear Algebra with Applications|language=en|volume=22|issue=6|pages=1102–1114|doi=10.1002/nla.2003|issn=1099-1506|arxiv=1409.7852|s2cid=1627477}}</ref> The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix <math>A</math> is a [[semi-separable matrix]] with rank <math>p</math> (that is, a matrix whose upper half, not including the main diagonal, is that of some matrix with [[matrix rank]] <math>p</math> and whose lower half is also that of some possibly different rank <math>p</math> matrix<ref name=":3" />) and so can be embedded into a larger [[band matrix]] (see figure on the right), whose sparsity structure can be leveraged to reduce the computational complexity. As the matrix <math>A \in \mathbb{R}^{n\times n}</math> has a semi-separable rank of <math>p</math>, the [[computational complexity]] of solving the linear system <math>Ax=b</math> or of calculating the determinant of the matrix <math>A</math> scales as <math>\mathcal{O}\left(p^2n \right)</math>, thereby making it attractive for large matrices.<ref name=":3" />
The fact that matrix <math>A</math> is a semi-separable matrix also forms the basis for {{proper name|celerite}}<ref>{{Cite web|url=https://celerite.readthedocs.io/en/stable/|title=celerite — celerite 0.3.0 documentation|website=celerite.readthedocs.io|language=en|access-date=2018-04-05}}</ref> library, which is a library for fast and scalable [[Gaussian process regression]] in one dimension<ref name=":1">{{Cite journal|
==See also==
| |||