Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LinearAlgebra.det improvements #282

Draft
wants to merge 1 commit into
base: master
Choose a base branch
from
Draft

Conversation

nsajko
Copy link
Contributor

@nsajko nsajko commented Nov 25, 2023

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
Copy link
Contributor Author

nsajko commented Nov 25, 2023

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.

@nsajko nsajko force-pushed the det branch 2 times, most recently from 712eb81 to 2889bfb Compare November 26, 2023 08:24
@nsajko nsajko marked this pull request as draft November 27, 2023 04:49
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-repl
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, and with all other
recent PRs of mine applied, to MultivariatePolynomials.jl,
DynamicPolynomials.jl, and MutableArithmetics.jl. The same computation
with MultivariatePolynomials v0.5.3 ran for multiple minutes before I
decided to just kill it.

Depends on JuliaAlgebra#285.

Fixes JuliaAlgebra#281.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

use the LinearAlgebraX package for linear algebra?
1 participant