Repository navigation
Conversation
Use Kahan's compensated summation algorithm via fused multiply-add (fma) with power-of-2 dynamic scaling to prevent catastrophic cancellation and intermediate underflow/overflow on ill-conditioned 2x2 matrices.
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #33062
Use Kahan's compensated summation algorithm via fused multiply-add (fma) with power-of-2 dynamic scaling to prevent catastrophic cancellation and intermediate underflow/overflow on ill-conditioned 2x2 matrices.
PR summary
What problem does this PR solve? Link any relevant issues and PRs.
numpy.linalg.detexhibits catastrophic forward cancellation on ill-conditioned 2x2 matrices where entries are large and nearly dependent. Becausedetdelegates to LAPACK's LU factorization (dgetrf) viaslogdet, pivoting and Schur complement computations lose precision, and converting through log space amplifies errors to produce incorrect magnitudes and signs (for instance,[[1e9+1, 1e9], [1e9, 1e9-1]]evaluates to ~119.2 instead of -1.0).This PR intercepts 2x2 real floating-point matrices in$2^{-s}$ , where $s = \lfloor\log_2(\max \vert{}M\vert{})\rfloor$ ) before evaluation to guard against intermediate underflow and overflow without incurring mantissa rounding error, guaranteeing maximum relative error <= 1.5 ulps.
det()and calculates their determinant using William Kahan's compensated algorithm via fused multiply-add (fma). The inputs are scaled by an exact power of 2 (Why are you interested in working on this PR?
Accurate 2x2 determinants are essential in computational geometry, graphics, collision detection, and coordinate transformations where near-singular systems frequently arise and LU-based methods fail unexpectedly.
How does the proposed change help you?
It provides reliably accurate results for low-dimensional determinants directly through the standard
np.linalg.detinterface, removing the need to write custom FMA wrappers or fall back on high-overhead arbitrary-precision packages.First time contributor introduction
Hi! I am a computer engineering student working with scientific computing and linear algebra workflows in Python. I regularly use NumPy across data processing, computer vision, and machine learning projects, and I am excited to contribute to the core library.
AI Disclosure
AI assistance (Google Gemini) was used to explore Kahan's FMA formulation and draft the initial scaling logic and PR description. The implementation was manually checked, integrated into
numpy/linalg/_linalg.py, compiled usingspin build, and tested against cancellation matrices prior to submission.