Dev Days 1: Exact Linear Algebra

• Michael Abshoff -> LinBox debianization

• Martin Albrecht -> GF(2), M4RI

• Nick Alexander

• Gregory Bard -> M4RI

• Rob Beezer
• Tom Boothby
• Craig Citro
• Burcin Erocal

• Robert Miller (especially sparse GF(2)) -> sparse GF(2)

• David Roe (p-adic linear algebra?) -> cyclotomic linear algebra

• Arne Storjohann ->

• William Stein -> Cyclotomic linear algebra, HNF

• Ralf-Philipp Weinmann -> Sparse Elimination, Nullspace

Dense GF(2)

• implement LQUP decomposition [Clement, Martin]
  • implement LQUP routine [Clement]
  • implement TRSM routine [Clement]
  • implement efficient column swaps/rotations [Martin]
    • SSE2 might help a lot here
  • implement memory efficient mzd_addmul_strassen [Martin]
    • See Clement's et al. paper on memory efficient Strassen-Winograd
• implement Arne's asymptotically fast elimination algorithm [Martin]
• implement multi-core multiplication with optimal speed-up
  • OpenMP seems to be nice and easy
  • 2 cores probably main target, but think about 4 cores too
• improve efficiency of M4RM
  • try 7 instead of 8 Gray code tables to leave room for the actual matrix in L1
  • try to fit three matrices rather than two into L2 or understand why it works so good for two
  • detect L1/L2 cache sizes at runtime and choose optimal parameters for them
  • implement Bill's half table idea and benchmark it

Sparse GF(2) (and other small finite fields)

• Sparse Reduced Echelon form (RPW)
  • Sparse Elimination:

    • improve LinBox gauss-domain

    • eclib sparse elimination
    • ....
• ....

Hermite Normal Form

• Arne, Clément, William

• new algorithm, based on system solving (Arne Storjohann) -> already an implementation

  • integrate it in IML
  • benchmark it against Sage
• generalization: block vector system solving
  • implementation
  • benchmark

• LLL trick for the existing implementation in Sage (William & Clément)

Polynomial Matrix computations

• Nullspace computation (Burcin)

Cyclotomic linear algebra

== p-adic linear algebra ==

LinBox debianization and 1.1.6 spkgization

• mabshoff, Clément