wiki:Desgin
Last modified 21 months ago

December 2009 LinBox meeting Reports

LinBox 1.1.7 release

Under progress. Remaining issues are:

  • to be completed...

LinBox 2.0 Design agenda

Summary of the discussion of sunday dec. 6. We tried to sort the different topics to be addressed in designing LinBox 2.0.

Development model:

LinBox 2.0 will be an incremental rewrite. In order to ensure code quality, the following development model will be used:

  • Check-in's to the svn tree only done by the release manager.
  • GIT revision control system
  • Each developper manages his local revision tree
  • There is a centralized master for each developper on the git server.
  • Builbot is launched at each update of a user master repo
  • The release manager merges these versions into the main master and produces each releases
  • code quality (creterions to be defined: documentation, pass on buildbot, valgrind...). The release manager can ask for rewrite

Parallelism

  • Identify building blocks to be parallelized: block-Krylov, CRT.
  • Parallel programming model: Kaapi, OpenMP, Cilk++ ...: can it be done in a PnP manner?

An early version of Kaapi/LinBox? CRT engine is being developped (Thierry Gautier & JGD)

LBA

External API's:

  • Redesign solutions: functions for users & function classes for internal usage
  • Interface's:
    • maple
    • sage: the switch to sage's native floating point modn-dense matrices, should be already in 1.1.7
    • Structured linear algebra features (incorporate E Shost library)

Internal API's:

Various areas of the library where the interface has to be re-designed

Field interfaces

  • add F.one, F.zero F.mone methods
  • init: from int, uint, long, ulong, double, float, gmpint, long long, u long long
  • use more extensively Givaro finite fields (and remove the deprecated ones in LinBox)
  • Specialized field to handle tuples of elements in a machine word (double) for packed Linalg.

DenseMatrix new design

Still a lot to do:

  • Inverse BlackBox (FIBB?): providing !inverseApply to Dixon's lifting. Implementations include PLUQ for dense matrices, sparseElim for sparse matrices, Wiedeman for BlackBox.
  • Dave's design of Contexts ?
  • Proposed approch to packed dense linalg:
    • stored unpacked
    • when a call to matmul is made, B is being packed if dimension over a threshold
  • Need to investigate other approches:
    • always packed, and depack A for matmul
    • always packed and specialized LU, matmul...

Vision on the overall approach to dense linalg over finite field:

  • p=2,3,5,7... interface M4RI,M3RI...
  • p < 2000 compressed representation combined with FFLAS over float, FFLAS over double (to be developped)
  • p < 223 FFLAS over double
  • p > 23 RNS using a few efficient primes: 220-1, 221-1,....

CRT factory

  • early-term, hadamard computation, precomputation of the basis, redundant CRT, parallelism ...
  • no random primes for the CRT, except for the early termination check
  • store tables of primes of 20, 21,.. bits. And store the lagrange basis as well?

Lifting factory

support Dixon's lifting, High order lifting,

Sparse elimination factory

Miscelaneaous

  • AutoHell: fix autoconf or switch to SCons, CMake,...?
  • Matrix file formats
  • Funding: french ANR grant proposal, joint with a NSF proposal? Deadline Jan 12, 2010
  • Next LinBox meeting in Dublin: early june 2010