Generalized Rybicki Press algorithm.

DOI10.1002/NLA.2003MaRDI QIDQ5739744zbMATH OpenOpenAlexFDO

Authors Sivaram Ambikasaran

Publication date 19 July 2016

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.7852

zbMATH Keywords

linear complexityfast direct solverCARMA processessemi-separable matricesexponential covariancefast determinant computationRybicki Press algorithm

Mathematics Subject Classification ID

Analysis of variance and covariance (ANOVA) (62J10) Computational methods for sparse matrices (65F50) Numerical computation of determinants (65F40)

Abstract: This article discusses a more general and numerically stable Rybicki Press algorithm, which enables inverting and computing determinants of covariance matrices, whose elements are sums of exponentials. The algorithm is true in exact arithmetic and relies on introducing new variables and corresponding equations, thereby converting the matrix into a banded matrix of larger size. Linear complexity banded algorithms for solving linear systems and computing determinants on the larger matrix enable linear complexity algorithms for the initial semi-separable matrix as well. Benchmarks provided illustrate the linear scaling of the algorithm.

Recommendations

• Using the generalized dynamic programming theory to calculate determinants and invert matrices
• An inversion algorithm for a banded matrix
• Linear complexity algorithms for semiseparable matrices
• A fast algorithm for the inversion of general Toeplitz matrices
• Fast inversion algorithms for diagonal plus semiseparable matrices

Cites work

• scientific article; zbMATH DE number 3158376 (Why is no real title available?)
• (Modified) Fredholm determinants for operators with matrix-valued semi-separable integral kernels revisited
• A Supernodal Approach to Sparse Partial Pivoting
• A modification of the Dewilde-van der Veen method for inversion of finite structured matrices
• Algorithm 836
• An overview of SuperLU
• Fast and Stable Algorithms for Banded Plus Semiseparable Systems of Linear Equations
• Finite Boundary Value Problems Solved by Green's Matrix.
• Introduction to Time Series and Forecasting
• Inversion formulas and linear complexity algorithm for diagonal plus semiseparable matrices
• Linear complexity algorithms for semiseparable matrices
• Lévy-driven CARMA processes
• Matrix Inversion, Its Interest and Application in Analysis of Data
• Non-compact integral operators with semi-separable kernels and their discrete analogues: Inversion and Fredholm properties
• On continuous-time threshold ARMA processes
• On inverting a class of patterned matrices
• The Inverse of a Certain Matrix, with an Application
• Two fast algorithms for solving diagonal-plus-semiseparable linear systems.

Describes a project that uses

Uses Software

• COLAMD
• Matlab
• SuperLU
• Eigen
• symamd
• ESS
• GitHub

This page was built for publication: Generalized Rybicki Press algorithm.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739744)