[R] Strucchange: Breakpoint slow

[Achim Zeileis]

On Wed, 27 Jun 2012, Cand2d wrote:

> Hi to all,
>
> I am trying to run breakpoints() on a fairly large sample (>10.000 
> observations). The process is very slow, any idea on how to speed this 
> up? I have tried the hpc="foreach" parameter, but this didn't work at 
> all when I tried to run it on a smaller sample.

The dynamic programming algorithm implemented in breakpoints() has 
computations and storage requirements of order O(n^2). And it is 
implemented in pure R. So with n > 10,000 you would need to have loads of 
cores to bring it to something computable. And even then, you would 
probably have to wait very long.

There are more efficient implementations of the dynamic programming 
algorithm available, however, I think only for the simple location model 
(x ~ 1) and not for general regressions. Similarly, alternative algorithms 
(such as PELT in package "changepoints" which is of order O(n)) are not 
available for general regressions to the best of my knowledge.

Either you could try recursive splitting of the data. Or you could coarsen 
the time grid...

hth,
Z

> breakpoints(x ~ x.l1 + x.l2 + X.l3 + x.l4 + x.l5 + x.l6 + x.l7 + x.l8 + y.l1
> + y.l2 + y.l3 + y.l4 + y.l5 + y.l6 + y.l7 + y.l8 + index(x))
>
> Thanks.
>
> Regards
>
> Christoph
>
>
>
>
> --
> View this message in context: http://r.789695.n4.nabble.com/Strucchange-Breakpoint-slow-tp4634602.html
> Sent from the R help mailing list archive at Nabble.com.
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>