Generalized Rybicki Press algorithm.

DOI10.1002/NLA.2003zbMATH Open1374.65078arXiv1409.7852OpenAlexW2963033836MaRDI QIDQ5739744FDOQ5739744

Authors: Sivaram Ambikasaran 

Publication date: 19 July 2016

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

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.

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

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

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)

Cites Work

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

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)