Algorithm Improvements for Fast Lomb Scargle by kkrutkowski · Pull Request #17842 · astropy/astropy · GitHub
Skip to content

Algorithm Improvements for Fast Lomb Scargle - #17842

Merged
astrofrog merged 12 commits into
astropy:mainfrom
kkrutkowski:lra_nfft
May 1, 2026
Merged

astrofrog merged 12 commits into
astropy:mainfrom
kkrutkowski:lra_nfft

Conversation

@kkrutkowski

@kkrutkowski kkrutkowski commented Mar 3, 2025 •

Copy link
Copy Markdown
Contributor

Description

This pull request adds the Low-Rank Approximation implementation of the Nonuniform Fast Fourier Transform as an alternative backend to the trig_sum() utility in the Lomb-Scargle utils file and adjusts the tests and docs accordingly.

The new implementation is up 4x slower, when compared to existing one, but also 8 to 10 orders of magnitude more accurate, nearly matching the accuracy of the slow method.

While not having a significant impact on the typical accuracy of the standard fast implementation (except eliminating the negative powers issue) it significantly improves the fastchi2 method, causing it to nearly match the slow chi2 implementation in the terms of accuracy.

The new algorithm is now set as default for both fast and fastchi2 methods, although it may be better keep the original defaults in the fast method to avoid the slow-down. Additionally it requires SciPy installed to be functional (for the jv bessel functions - if prefer_lra=True is passed, but the SciPy is not available it falls back to the current code printing a warning suggesting explicitely passing prefer_lra=False

The behaviour got modified after preliminary review and now the Low Rank approximation gets chosen by passing algorithm='lra' to either of the fast methods or the trig_sum function. Additionally the Bessel function approximation relies on the Taylor series around x=0 and as such no longer relies on SciPy for evaluation.

The new algorithm is default for the fastchi2 and auto methods, although the less accurate approximation is kept as the default option for the fast method if it is called directly. The old (default) trig-sum algorithm additionally can be specified manually by passing algorithm='fasper' (sharing the name of the original Fortran subroutine published by Press and Rybicki in 1989), although currently it remains the default behaviour.

Technically the code almost certainly could have been made faster than the 'old' fast method if rewritten in C (as the way the operations are performed with NumPy is at least awkward and probably far from optimal), although I'm not sure if it's even worth consideration, as the SciPy-independent jv implementation would probably take over 1000 lines of code, with the full implementation nearing 2 thousand (and causing a significant bloat to the library as a whole).

EDIT: Using the locally converging Taylor series would probably allow to fit the whole implementation in ~ 500 LOC making the rewrite significantly more feasible

Fixes #5941, #9523 and #11302

@github-actions

github-actions Bot commented Mar 3, 2025

Copy link
Copy Markdown
Contributor

@pllim pllim added this to the v7.1.0 milestone Mar 3, 2025
@pllim pllim added Performance benchmark Run benchmarks for a PR labels Mar 3, 2025
@kkrutkowski

kkrutkowski commented Mar 3, 2025 •

Copy link
Copy Markdown
Contributor Author

Sorry for so many typos in the original PR. To me the test results look fine now, although there is one minor issue remaining - the doc test fails on systems with no SciPy available (at there the less accurate 'FASPER' is used instead of the new code) as the default for the method 'auto';

=================================== FAILURES ===================================
________________________ [doctest] lombscargle.rst _________________________
526 
527 To use the Lomb-Scargle periodogram to decide if our signal contains a periodic
528 component, we can start by simulating 60 observations of a sine wave with noise:
529 
530 >>> t = 100 * rand.random(60)
531 >>> dy = 1.0
532 >>> y = np.sin(2 * np.pi * t) + dy * rand.standard_normal(60)
533 >>> ls = LombScargle(t, y, dy)
534 >>> freq, power = ls.autopower()
535 >>> print(power.max())  # doctest: +FLOAT_CMP
Expected:
    0.28800558204470955
Got:
    0.29154492887882927

Although I'm willing to apply any suggestions regarding that issue or potentially anything else.

As for the rest it looks just fine - I've disabled the warning with 'method=auto', as it was causing some issues with native settings and multiband LS (and I've forgotten to apply it when creating the PR).

Also the new 'fast' algorithm seems to pass the tests used by 'slow' implementations with almost an order of magnitude of error margin, so I think that at least in the terms of precision it should meet the expectations.

Thanks for quick reaction and sorry for fixing it too late (and creating an 'active' PR instead of draft as I've meant to)

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

There are ways to handle that doctest but maybe want to wait until the initial round of review first. Should fix the pre-commit check though. Are you able to squash your commits while you are at it? Thanks!

@kkrutkowski kkrutkowski closed this Mar 3, 2025
@kkrutkowski kkrutkowski reopened this Mar 3, 2025
@kkrutkowski kkrutkowski closed this Mar 3, 2025
@kkrutkowski kkrutkowski reopened this Mar 3, 2025
@kkrutkowski

Copy link
Copy Markdown
Contributor Author

There are ways to handle that doctest but maybe want to wait until the initial round of review first. Should fix the pre-commit check though. Are you able to squash your commits while you are at it? Thanks!

Thanks for reply, but I'm not sure how can I squash this commit - the git/ssh interface doesn't seem to work and I have no access to the squash option in the GUI (although I may just be doing something wrong - I'll definitely try to fix that later).

Am I supposed to just reopen this pull request from a different branch (if rebasing won't start working again soon)? Sorry once again.

Btw I'll fix the formatting soon, although I'm not really sure how the imports should be sorted to make it work - any advices? Sorry for the chaos.

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

For a significant change as this, it would be tough to solely rely on GH web interface. Are you not able to clone your fork locally and then work on your branch from your machine?

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

Please have a look at our contributing guide at https://docs.astropy.org/en/latest/index_dev.html in case it helps. It also spams our CI and notification system when you push out a lot of commits via the GH web interface like this.

@kkrutkowski

Copy link
Copy Markdown
Contributor Author

For a significant change as this, it would be tough to solely rely on GH web interface. Are you not able to clone your fork locally and then work on your branch from your machine?

Thanks for quick reply, cloning and working/squashing locally works just fine, but pushing/rebasing the squashed repository for some reason fails. It may have something to do with my (incorrect) system configuration, so I'll have to try to fix that.

I've also seen the contributing guide, although I'm not sure how to make a use of it. Squash rebasing is something I'll try to perform in the next few days, but I'm not sure while it fails.

Also ruff locally doesn't give any issues when running on the same code, but in AstroPy's repo returns 3 issues (even after applying 'ruff format' on the same file just before uploading), so I have no idea what happens here.

Thanks for help and sorry for the trouble once again.

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

After a rebase, you have to do a force push. If you are not sure it would work, a backup branch where you can recover from would be prudent. As for the pre-commit, I can try to apply autofix and see.

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

pre-commit.ci autofix

@kkrutkowski

Copy link
Copy Markdown
Contributor Author

After a rebase, you have to do a force push. If you are not sure it would work, a backup branch where you can recover from would be prudent. As for the pre-commit, I can try to apply autofix and see.

Thanks, looks like now somehow everything is just fine. Force push is where the error happens. I'll try to fix it later and/or try with gh instead of git. Or try from differenc PC, maybe this will (somehow) solve the issue.

@pllim

pllim commented Mar 3, 2025

Copy link
Copy Markdown
Member

FWIW force push is pretty much mandatory if you squash commits because the PR history has changed. But do what you will for now. As long as the diff is clean here, review should be possible. Thanks again!

@kkrutkowski

Copy link
Copy Markdown
Contributor Author

FWIW force push is pretty much mandatory if you squash commits because the PR history has changed. But do what you will for now. As long as the diff is clean here, review should be possible. Thanks again!

Thanks for help once again, using gh (github-cli) instead of git (or rather with, as I've used the gh only to log into my repo) directly somehow have worked I guess. I'm leaving it here if someone had the same issue in the future.

So I guess that might be enough. Sorry for inconvenience.

@neutrinoceros neutrinoceros left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is a high-level review in that I didn't scrutinize with the details of the implementation, but focused on the way the APIs are evolved. I wrote a couple targeted comments that actually apply in more than one place. In particular, I recommend avoiding the addition of a boolean prefer_lra parameter, that should instead be something like method='lra'.

Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fastchi2_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/utils.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/utils.py Outdated
@kkrutkowski

Copy link
Copy Markdown
Contributor Author

This is a high-level review in that I didn't scrutinize with the details of the implementation, but focused on the way the APIs are evolved. I wrote a couple targeted comments that actually apply in more than one place. In particular, I recommend avoiding the addition of a boolean prefer_lra parameter, that should instead be something like method='lra'.

Thanks for reply, that definitely makes more sense from the users' perspective. Although I have one more question - how do you see it implemented for the fastchi2 method (which is the one affected significantly more, when compared to the standard 'fast' by that update?

The way I see it using the name 'fasper' as an alias for current 'fast' method (named after the original Fortran subroutine with the same name published by Press and Rybicki - that name to me looks more concise and seems to be used more often, than explicitely refering to this by their names, but that may be just me not knowing any representative sample) and making 'method=lra' an alias for the new trig_sum variant. Would something like that be fine?

Also as for the separate submodule - are you suggesting creating a separate file with an alternative definition of the trig_sum and conditionally importing it from implementations/utils if lra is selected as the trig_sum() approximation method?

I don't really see a reason for repeating all of the fast/fastchi2 methods code, as essentially it's still the same method by their high-level details - they differ only in their 'extirpolation', and as such at least ~ ¾ of existing code can be reused.

Also I assume, that the SciPy-independent implementation of the jv() function might get added in the future, but you're definitely right that I shouldn't threat the SciPy import as only a temporary solution here.

@neutrinoceros

Copy link
Copy Markdown
Contributor

how do you see it implemented for the fastchi2 method (which is the one affected significantly more, when compared to the standard 'fast' by that update?

I'm not sure I'm familiar enough with the details to answer this question right now. Let me clarify that when I proposed method as a argument in place of prefer_lra, I was taking a guess; if this argument name isn't appropriate, I trust you can come up with a better one. The important part of my point is that we should avoid boolean arguments everywhere that more than 2 options may exist (even if there are exactly 2 at the time of writing).

The way I see it using the name 'fasper' as an alias for current 'fast' method (named after the original Fortran subroutine with the same name published by Press and Rybicki - that name to me looks more concise and seems to be used more often, than explicitely refering to this by their names, but that may be just me not knowing any representative sample) and making 'method=lra' an alias for the new trig_sum variant. Would something like that be fine?

I don't think we should always favor conciseness over clarity. I can be argued that conciseness is fine for domain-specific jargon though; if you think it's reasonable to expect that any potential user would immediately understand what fasper means, then I don't have any objections. Otherwise, I recommend being as explicit as possible.

Also as for the separate submodule - are you suggesting creating a separate file with an alternative definition of the trig_sum and conditionally importing it from implementations/utils if lra is selected as the trig_sum() approximation method?

no. I'm suggesting to move conditional definitions to a separate module that would have a hard-requirement on scipy, but only be imported from conditionally.

I don't really see a reason for repeating all of the fast/fastchi2 methods code, as essentially it's still the same method by their high-level details - they differ only in their 'extirpolation', and as such at least ~ ¾ of existing code can be reused.

by all means, do reuse existing code whenever you can. I certainly didn't mean to suggest otherwise. Is there anything I need to clarify from my initial reply ?

@kkrutkowski

Copy link
Copy Markdown
Contributor Author

how do you see it implemented for the fastchi2 method (which is the one affected significantly more, when compared to the standard 'fast' by that update?

I'm not sure I'm familiar enough with the details to answer this question right now. Let me clarify that when I proposed method as a argument in place of prefer_lra, I was taking a guess; if this argument name isn't appropriate, I trust you can come up with a better one. The important part of my point is that we should avoid boolean arguments everywhere that more than 2 options may exist (even if there are exactly 2 at the time of writing).

The way I see it using the name 'fasper' as an alias for current 'fast' method (named after the original Fortran subroutine with the same name published by Press and Rybicki - that name to me looks more concise and seems to be used more often, than explicitely refering to this by their names, but that may be just me not knowing any representative sample) and making 'method=lra' an alias for the new trig_sum variant. Would something like that be fine?

I don't think we should always favor conciseness over clarity. I can be argued that conciseness is fine for domain-specific jargon though; if you think it's reasonable to expect that any potential user would immediately understand what fasper means, then I don't have any objections. Otherwise, I recommend being as explicit as possible.

Also as for the separate submodule - are you suggesting creating a separate file with an alternative definition of the trig_sum and conditionally importing it from implementations/utils if lra is selected as the trig_sum() approximation method?

no. I'm suggesting to move conditional definitions to a separate module that would have a hard-requirement on scipy, but only be imported from conditionally.

I don't really see a reason for repeating all of the fast/fastchi2 methods code, as essentially it's still the same method by their high-level details - they differ only in their 'extirpolation', and as such at least ~ ¾ of existing code can be reused.

by all means, do reuse existing code whenever you can. I certainly didn't mean to suggest otherwise. Is there anything I need to clarify from my initial reply ?

Thanks, everything seems clear now. Also I could implement a simple fallback NumPy jv() series using gamma (and possibly factorial) from math - I'll check if it is accurate enough (and almost definitely it would be significantly slower, than the SciPy implementation), although it can be done in like ~ 15 lines of code with no external dependencies. If you thing something like that would be more suitable, than the current fallback to the much less accurate (but faster) method it might be worth consideration.

@neutrinoceros

neutrinoceros commented Mar 4, 2025 •

Copy link
Copy Markdown
Contributor

On the conditions that:

  • default behavior is unchanged
  • explicit user requests are never ignored (raise an exception when they cannot be satisfied)

I don't see any problem with having more options available

@neutrinoceros neutrinoceros left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

CI appears to be in a much better shape now, here's another round of review !
Please pay attention to reports from pre-commit.ci (I cannot recommend enough going through https://docs.astropy.org/en/latest/development/quickstart.html#install-pre-commit). It's not a big deal to defer lints to until the PR is stabilized, but it seems to be the case now (well done !).

Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fastchi2_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/fastchi2_impl.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/implementations/tests/test_utils.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/tests/test_lombscargle.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/tests/test_lombscargle.py Outdated
Comment thread astropy/timeseries/periodograms/lombscargle/tests/test_lombscargle.py Outdated
Comment thread docs/changes/timeseries/17842.feature.rst Outdated
@astrofrog

Copy link
Copy Markdown
Member

Before I review this again I wanted to mention that we should add an entry to the what's new in 8.0 page. Would you be able to do this? The file is in docs/whatsnew/8.0.rst

@neutrinoceros

Copy link
Copy Markdown
Contributor

@astrofrog I propose we merge this today regardless and postpone any corrections to between FF and RC

@astrofrog astrofrog left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's do this - thanks @kkrutkowski!

@astrofrog
astrofrog enabled auto-merge May 1, 2026 16:48
@kkrutkowski

Copy link
Copy Markdown
Contributor Author

Let's do this - thanks @kkrutkowski!

Thank you very much for pointing out the issues and sorry for takind so long to add the whatsnew entry (i still struggle a little bit with deciding what to put in there). If there are any issues with the code I'll correct them asap though.

@neutrinoceros
neutrinoceros dismissed their stale review May 1, 2026 17:38

dismissing my own review so as not to block a merger

@astrofrog
astrofrog merged commit 3a6fc91 into astropy:main May 1, 2026
37 of 38 checks passed
@neutrinoceros

Copy link
Copy Markdown
Contributor

I opened #19642 to keep track of what remains to be done before rc. Thanks, all !

@pllim

pllim commented May 4, 2026

Copy link
Copy Markdown
Member

For future reference, if this needed What's New, you should have added whatsnew-needed label. That would have blocked merge until it was added.

@neutrinoceros

Copy link
Copy Markdown
Contributor

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Algorithm Improvements for Fast Lomb Scargle

6 participants