[ODK] Meeting 2018 09 14

Cleanup Rational Solver call chain for dense matrices (Ax = b)

⇨ Main board project

• linbox/solutions/solve.h
• linbox/algorithms/rational_solver.h
• linbox/algorithms/rational_solver.inl

Deadline: August 31st, 2019.

1. Identify (and fix if needed)

• Design issues
• Code duplication
• Bugs
• Test coverage lack
• Benchmark coverage lack
• Gold nuggets (aka great code)

2. (Re)write

• Test suite
• Benchmark suite

3. Parallel algorithms aspects

• First approach: CRT
  • Zhu's work: MPI, OpenMP, Thread. Solve for different moduli step is parallelized.
  • What to do with matrix A? Each worker copies it, or distribute it ?
• Second approach: p-adic lifting
• Third approach: hybrid approach CRT/lifting (Chen-Storjohann ISSAC'05)

4. Missing pieces

• Ultra high priority
• High priority
• Somewhat high priority

For CRT

Sequential	Parallel
Multipoint evaluation	Multipoint evaluation
	CRT
Rational reconstruction (random projection + cleanup)
Hadamard bound solution

For p-adic lifting

• Parallelize this using MatVecProd and MatInv mod p (parallel in FFLAS)

5. Misc.

• Rework Rational reconstruction (for now it looks like spaghetti code)
• Maybe implement Olesh & Storjohann '07 for rational reconstruction.
• Make some parallel algorithms in SageMath (RatSolve, Rk, Det...)

6. First things to do

• Create issues (and meta-issues) tracking the aformentioned tasks.
• Design work for parallel CRT
• Alexis -> Cleanup
• Zhu -> Clean parallel tests and finish WIP on CRT
• David -> Wildcard