A Fast Least-Squares Algorithm for Multiple-Row Downdatings


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 2, No. 1, pp. 55-65, Jan. 1995
10.3745/KIPSTE.1995.2.1.55,   PDF Download:

Abstract

Existing multiple-row downdating algorithms have adopted a CFD(Cholesky Factor Downdating) that recursively downdates one row at a time. The CFD based algorithm requires 5/2pn2 flops(floating point operations) downdating a p %u2265n obervation matrix ZT. On the other hands, a HCFD(Hybrid CFD) based algorithm we propose in this paper, requires 5/6pn2 n3 flops v hen p≥n. Such a HCFD based algorithm factorizes ZT at first, such that ZT=QzRTz, and then applies the CFD onto the upper triangular matrix RTz, so that the total number of floating point operations for downdating ZT would be significantly reduced compared with that of the CFD based algorithm. Benchmark tests on the Sun SPARC/2 and the Tolerant System also show that the performance of the HCFD based algorithm is superior to that of the CFD based algorithm, especially when the number of rows of the observation matrix is large.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
L. C. Han and K. S. Il, "A Fast Least-Squares Algorithm for Multiple-Row Downdatings," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 2, no. 1, pp. 55-65, 1995. DOI: 10.3745/KIPSTE.1995.2.1.55.

[ACM Style]
Lee Chung Han and Kim Suk Il. 1995. A Fast Least-Squares Algorithm for Multiple-Row Downdatings. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 2, 1, (1995), 55-65. DOI: 10.3745/KIPSTE.1995.2.1.55.