×

Generalized Rybicki Press algorithm. (English) Zbl 1374.65078

Summary: 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.

MSC:

65F40 Numerical computation of determinants
65F50 Computational methods for sparse matrices
62J10 Analysis of variance and covariance (ANOVA)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Asplund, Finite boundary value problems solved by Green’s matrix, Mathematica Scandinavica 7 pp 49– (1959) · Zbl 0093.31101 · doi:10.7146/math.scand.a-10560
[2] Gohberg, Non-compact integral operators with semi-separable kernels and their discrete analogues: inversion and Fredholm properties, Integral Equations and Operator Theory 7 (5) pp 642– (1984) · Zbl 0549.45001 · doi:10.1007/BF01195920
[3] Gesztesy, Modified Fredholm determinants for operators with matrix-valued semi-separable integral kernels revisited, Integral Equations and Operator Theory 47 (4) pp 457– (2003) · Zbl 1084.47015 · doi:10.1007/s00020-003-1170-y
[4] Roy, On inverting a class of patterned matrices, Biometrika 43 (1-2) pp 227– (1956) · Zbl 0070.14801 · doi:10.1093/biomet/43.1-2.227
[5] Roy, Evaluation of determinants, characteristic equations and their roots for a class of patterned matrices, Journal of the Royal Statistical Society. Series B (Methodological) 22 (2) pp 348– (1960) · Zbl 0097.13601
[6] Mustafi, The inverse of a certain matrix, with an application, The Annals of Mathematical Statistics 38 (4) pp 1289– (1967) · Zbl 0166.03101 · doi:10.1214/aoms/1177698802
[7] Uppuluri, The inverse of a matrix occurring in first-order moving-average models, Sankhyā: The Indian Journal of Statistics, Series A 31 (1) pp 79– (1969)
[8] Greenberg, Matrix inversion, its interest and application in analysis of data, Journal of the American Statistical Association 54 (288) pp 755– (1959) · Zbl 0089.15602 · doi:10.2307/2282499
[9] Vandebril, A bibliography on semi-separable matrices*, Calcolo 42 (3-4) pp 249– (2005) · doi:10.1007/s10092-005-0107-z
[10] Eidelman, A modification of the Dewilde-van der Veen method for inversion of finite structured matrices, Linear Algebra and its Applications 343 pp 419– (2002) · Zbl 1010.65013 · doi:10.1016/S0024-3795(01)00363-9
[11] Camp, Two fast algorithms for solving diagonal-plus-semi-separable linear systems, Journal of Computational and Applied Mathematics 164 pp 731– (2004) · Zbl 1038.65025 · doi:10.1016/j.cam.2003.09.040
[12] Eidelman, Inversion formulas and linear complexity algorithm for diagonal plus semi-separable matrices, Computers & Mathematics with Applications 33 (4) pp 69– (1997) · Zbl 0870.65020 · doi:10.1016/S0898-1221(97)00008-4
[13] Gohberg, Linear complexity algorithms for semi-separable matrices, Integral Equations and Operator Theory 8 (6) pp 780– (1985) · Zbl 0592.65015 · doi:10.1007/BF01213791
[14] Jain, Numerical Methods for Structured Matrices and Applications pp 347– (2010) · doi:10.1007/978-3-7643-8996-3_15
[15] Chandrasekaran, Fast and stable algorithms for banded plus semi-separable systems of linear equations, SIAM Journal on Matrix Analysis and Applications 25 (2) pp 373– (2003) · Zbl 1050.65023 · doi:10.1137/S0895479899353373
[16] Brockwell, Introduction to Time Series and Forecasting, 2. ed. (2002) · Zbl 0994.62085 · doi:10.1007/b97391
[17] Brockwell, Lévy-driven CARMA processes, Annals of the Institute of Statistical Mathematics 53 (1) pp 113– (2001) · Zbl 0995.62089 · doi:10.1023/A:1017972605872
[18] Brockwell, On continuous-time threshold ARMA processes, Journal of Statistical Planning and Inference 39 (2) pp 291– (1994) · Zbl 0797.62072 · doi:10.1016/0378-3758(94)90210-0
[19] Ambikasaran S ESS 2014 https://github.com/sivaramambikasaran/ESS
[20] Rybicki, Class of fast methods for processing irregularly sampled or otherwise inhomogeneous one-dimensional data, Physical Review Letters 74 (7) pp 1060– (1995) · doi:10.1103/PhysRevLett.74.1060
[21] Guennebaud G Jacob B Avery P Bachrach A Barthelemy S Becker C Benjamin D Berger C Berres A Blanco JL Borgerding M Bossart R Brix K Brun G Büttgenbach P Capricelli T Carre N Ceccato J Chalupecky V Chrétien B Coles A J ”complexzeros” Danoczy M Dean J Drenkhahn G Ehrlicher C Fernandes M Ferro DG Garg R Gautier M Gladky A Glaser S Glisse M Gosselin F Hamelin P Hanwell MD Harmon D He C-P Heibel H Hertzberg C Holoborodko P Holy T Intel Irons T de Jong B Kim K Klammler M Köhler C Korepanov A Krivenko I Kruisselbrink M Kundu A Lenz M Li B Lipponer S Lowenberg D Luitz DJ Maks N Mantzaflaris A Marcin DJ Margaritis KA Martin R Marxer R Di Massa V Mayer C Meier-Dörnberg F Mierle K Montel L Nerbonne E Neundorf A Newton J Niesen J Nuentsa D Oberländer J van den Oever J Olbrich M Pilgrim S Piltz B Piwowarski B Ploskey Z Po G Popov S Rajagopalan M Rajko S Repinc J Riddile KF Roberts R Rodriguez A Román P Ruepp O Rusu RB Saupin G Saut O Schindler B Schmidt M Schridde D Schwendner J Seiler C Senst M Sheorey S Somerville A Stapleton A Strothoff S Swirski L Szalkowski A Traversaro S Trojanek P Truchet A Tsourouksdissian AR Tyrer JR Ulerich R de Valence H Vanhassel I Van Dyck M Wheeler S Witherden F Wolfer U Yguel M P , Zoppitelli Eigen v3 2010 http://eigen.tuxfamily.org
[22] Demmel, A supernodal approach to sparse partial pivoting, SIAM Journal on Matrix Analysis and Applications 20 (3) pp 720– (1999) · Zbl 0931.65022 · doi:10.1137/S0895479895291765
[23] Demmel, SuperLU Users’ Guide (2011)
[24] Li, An overview of superLU: algorithms, implementation, and user interface, ACM Transactions on Mathematical Software (TOMS) 31 (3) pp 302– (2005) · Zbl 1136.65312 · doi:10.1145/1089014.1089017
[25] Davis, Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS) 30 (3) pp 377– (2004) · Zbl 1070.65535 · doi:10.1145/1024074.1024080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.