JuliaAlgebra / MultivariatePolynomials.jl

Multivariate polynomials interface
https://juliaalgebra.github.io/MultivariatePolynomials.jl/stable/
Other
135 stars 27 forks source link

`LinearAlgebra.det` improvements #282

Open nsajko opened 10 months ago

nsajko commented 10 months ago

Performance improvements, support for more types.

Still broken for LinearAlgebra.Symmetric polynomial matrices, producing a MethodError because of a missing oneunit method. This, however, seems like a separate matter that would better be addressed by a separate pull request.

Performance comparison:

julia> versioninfo()
Julia Version 1.11.0-DEV.972
Commit 9884e447e79 (2023-11-23 16:16 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD Ryzen 3 5300U with Radeon Graphics
  WORD_SIZE: 64
  LLVM: libLLVM-15.0.7 (ORCJIT, znver2)
  Threads: 11 on 8 virtual cores

julia> using LinearAlgebra, DynamicPolynomials

julia> function f(n)
         @polyvar a b c d e
         diagm(
          -2 => fill(a, n - 2), -1 => fill(b, n - 1), 0 => fill(c, n),
           2 => fill(e, n - 2),  1 => fill(d, n - 1),
         )
       end
f (generic function with 1 method)

julia> const m15 = f(15);

julia> const m16 = f(16);

julia> @time det(m15);
  1.945673 seconds (45.22 M allocations: 2.261 GiB, 20.60% gc time, 4.02% compilation time)

julia> @time det(m15);
  1.991062 seconds (45.22 M allocations: 2.261 GiB, 23.74% gc time)

julia> @time det(m16);
  4.596664 seconds (106.67 M allocations: 5.324 GiB, 22.65% gc time)

julia> @time det(m16);
  4.648503 seconds (106.67 M allocations: 5.324 GiB, 22.66% gc time)

The above REPL session is with this commit applied. The same computation with MultivariatePolynomials v0.5.3 ran for multiple minutes before I decided to just kill it.

Depends on #285.

Fixes #281.

nsajko commented 10 months ago

Note that this PR also makes det work for many LinearAlgebra matrix types, like Diagonal. This is due to defining the determinat for scalar types.