JuliaArrays / JuliaArrays/StaticArrays.jl

Integer overflow in specialized _solve methods

Open
#681 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug linear-algebra numerical-robustness
Dominant language
Julia
Stars
844
Forks
159
Avg merge
3d 21h
Merged PRs (30d)
3

Description

As observed in #583 there's some weird errors with small-sized solves of integer matrices. For example:

julia> m = 2
       a = SMatrix{m,m}(rand(Int,m,m))
       b = SVector{m}(rand(Int,m))
2-element SArray{Tuple{2},Int64,1,2} with indices SOneTo(2):
  8315397486252833078
 -1243568792894157487

julia> Matrix(a) \ Vector(b)
2-element Array{Float64,1}:
 -1.0427738899729126
  0.5986498869255282

julia> a \ b
2-element SArray{Tuple{2},Float64,1,2} with indices SOneTo(2):
 4.043446204424333e-20
 8.620209721520739e-20

The underlying cause seems to be integer overflow in some specialized _solve functions. For example due using integer arithmetic here: https://github.com/JuliaArrays/StaticArrays.jl/blob/973a7092e1b92a95b69f4611e9da2c39707029bc/src/solve.jl#L10

CC @judober

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in src/solve.jl at the specialized _solve code around the referenced line and reproduce the small integer-matrix example from the issue. Trace the integer arithmetic in the specialized solve methods and compare it with the dense solve result; done means integer inputs no longer overflow and produce the correct solution.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.