Skip to content

BUG: linalg: improve 2x2 determinant accuracy using Kahan's algorithm - #33064

Open
sarhank8 wants to merge 1 commit into
numpy:mainfrom
sarhank8:fix-det-2x2-accuracy
Open

sarhank8 wants to merge 1 commit into
numpy:mainfrom
sarhank8:fix-det-2x2-accuracy

Conversation

@sarhank8

Copy link
Copy Markdown

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.det exhibits catastrophic forward cancellation on ill-conditioned 2x2 matrices where entries are large and nearly dependent. Because det delegates to LAPACK's LU factorization (dgetrf) via slogdet, 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 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 ($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.

  • 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.det interface, 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 using spin build, and tested against cancellation matrices prior to submission.

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

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

Labels

Projects

None yet

Development

Successfully merging this pull request may close these issues.

BUG: numpy.linalg.det() can be extremely inaccurate on 2x2 matrices

1 participant