Kim Suk Il, Lee Chung Han, Jeon Joong Nam

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 3, No. 2, pp. 359-368, Mar. 1996
10.3745/KIPSTE.1996.3.2.359,   PDF Download:

Abstract

This paper introduces PGD(Preprocessed Givens Downdating) and PHD(Preprocessed Hyperbolic Downdating) algorithms, wherein a multiple-row observation matrix Z^T is factorized into a partial Cholesky factor Rz, such that Z^T=QzRz, QzQ^Tz=1, QzQ^Tz=1, and then Rz is recursively downdating by using GD(Givens Downdating) and HD(Hyperbolic Downdating), respectively. Time complexities of PGD and PHD algorithms are pn^2 5n^3/6 and pn^2 n^3/3 flops, respectively, if p>=n, while those of the existing GD and HD are known to be 5pn^2/2 and 2pn^2 flops, respectively. This concludes that the factorization of observation matrices, which we call perprocessing, would improve the overall performance of the downdating process. Benchmarks on the Sun SPARC/2 system also show that preprocessing would shorten the requried downdating times compared to those of downdating without preprocessing. Furthermore, benchmarks also who that PHD provides better performance than PGD.

Statistics
Cite this article