Computer Science – Numerical Analysis
Scientific paper
2009-11-23
Computer Science
Numerical Analysis
27 pages, 8 figures
Scientific paper
The computational complexity of different steps of the basic SSA is discussed. It is shown that the use of the general-purpose "blackbox" routines (e.g. found in packages like LAPACK) leads to huge waste of time resources since the special Hankel structure of the trajectory matrix is not taken into account. We outline several state-of-the-art algorithms (for example, Lanczos-based truncated SVD) which can be modified to exploit the structure of the trajectory matrix. The key components here are hankel matrix-vector multiplication and hankelization operator. We show that both can be computed efficiently by the means of Fast Fourier Transform. The use of these methods yields the reduction of the worst-case computational complexity from O(N^3) to O(k N log(N)), where N is series length and k is the number of eigentriples desired.
No associations
LandOfFree
Computation- and Space-Efficient Implementation of SSA does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computation- and Space-Efficient Implementation of SSA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computation- and Space-Efficient Implementation of SSA will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-279151