Computation- and Space-Efficient Implementation of SSA

Details Computation- and Space-Efficient Implementation of SSA Computation- and Space-Efficient Implementation of SSA

2009-11-23

arxiv.org/abs/0911.4498v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-279151