Repository navigation
Algorithm Improvements for Fast Lomb Scargle - #17842
Conversation
|
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'; 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) |
|
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. |
|
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? |
|
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. |
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. |
|
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. |
|
pre-commit.ci autofix |
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 |
|
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 So I guess that might be enough. Sorry for inconvenience. |
neutrinoceros
left a comment
There was a problem hiding this comment.
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. |
I'm not sure I'm familiar enough with the details to answer this question right now. Let me clarify that when I proposed
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
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.
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. |
|
On the conditions that:
I don't see any problem with having more options available |
neutrinoceros
left a comment
There was a problem hiding this comment.
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 !).
|
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 |
|
@astrofrog I propose we merge this today regardless and postpone any corrections to between FF and RC |
Add the Low Rank Approximation as the alternative NUFFT algorithm of the trigsum utility
Added notes on the accuracy and speed trade-offs of different Lomb-Scargle implementations.
astrofrog
left a comment
There was a problem hiding this comment.
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. |
dismissing my own review so as not to block a merger
|
I opened #19642 to keep track of what remains to be done before rc. Thanks, all ! |
|
For future reference, if this needed What's New, you should have added |

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 - ifprefer_lra=Trueis passed, but the SciPy is not available it falls back to the current code printing a warning suggesting explicitely passingprefer_lra=FalseThe behaviour got modified after preliminary review and now the Low Rank approximation gets chosen by passing
algorithm='lra'to either of thefastmethods or thetrig_sumfunction. 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
fastchi2andautomethods, although the less accurate approximation is kept as the default option for thefastmethod if it is called directly. The old (default) trig-sum algorithm additionally can be specified manually by passingalgorithm='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
jvimplementation 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