TODO

Todo on LinBox (current as of 14.6.2011)

In general:
  • Bugs
    ∘ Compiler sometimes refusing to instantiate with TransposeMatrix
    ∘ benchmark-matrix-domain doesn't print anything unless one gives -l -m -n -k???
    ∘ Apparent bugs in M4RI
      ‣ mzd_read_bit seems to ignore offset
      ‣ Segfault on termination if mzd_free is called on _rep before resize
      ‣ Lots of failures with ElectricFence (free did not come from malloc)
      ‣ copy, equality tests do not work when one argument not word-aligned
      ‣ mul and addmul do not work when destination-matrix isn't word-aligned
    ∘ GF2 dot into BitVectorReference does not appear to work (see trsvSpecialized(RowMatrixTag, DenseZeroOneVectorTag))
    ∘ trmm, trsm tests in test-matrix-domain.h if M1 is not square
  • Missing specialisations, new wrappers
    ∘ Incorporate FFLAS/FFPACK into the rest of LinBox
      ‣ Some of FFLAS can go away -- it just duplicates functionality in MatrixDomain
      ‣ Part of FFLAS should become a MatrixDomain-BLAS wrapper
      ‣ Other important part of FFLAS is Straßen-Winograd implementation, which should go into another MatrixDomain-wrapper
      ‣ Most of FFPACK should be put aside for the time being, but contents of ffpack.h are useful and should go into algorithms
      ‣ Everything needs to be reindented and reformated, of course
  • Documentation-issues
    ∘ Need to document vector-formats -- maybe in vector-traits.h
  • Improvements to GaussJordan:
    ∘ Make ReduceRowEchelonForm use trsm and block-decomposition -- then maybe also eliminate specialisations
    ∘ Move support-routines (GetPivot, SetIdentity, FastAddin) into other classes and create unit-tests for them
  • Need a generic way to create deep copies of things
  • Things not caught in existing test-suite:
    ∘ BitReference using &-operator with bool
    ∘ Ditto dense/sparse dot-product over GF2
    ∘ Array-access not working with BitVector?
    ∘ Use of M4RI-solve calls on the wrong side in trsm, trmm
    ∘ hasDim doesn't work on sparse subvectors
    ∘ GaussJordan seems to be giving wrong answer on really large matrices (try F4-solver whilst disabling M4RI)???
    ∘ trsv, trmm, trmv on empty matrices crashes
    ∘ std::swap not specialised for subvectors (so BLAS3::permute on dense matrices doesn't actually permute anything)
    ∘ MutableSubvector::resize copies to the wrong destination-index
    ∘ MakeSubvector for columns in DenseMatrix used coldim () for displacement rather than disp () as it should have
    ∘ Modifications to BitSubvector::word_reference cause trmm to fail
    ∘ (Submatrix case) Test for permutations on GF2 passes even though output shows it's clearly wrong
    ∘ copy_impl (DenseZeroOne, HybridZeroOne) wasn't getting last word
    ∘ back_word on BitSubvectorWordAligned returning *_end rather than *(_end - 1)
    ∘ equal_impl == false, is_zero_impl == false should also be tested
    ∘ equal (DenseZeroOne, HybridZeroOne) would fail if the input-vector was one word or less
    ∘ swap (BitSubvectorWordAligned) did not touch back_word ()
    ∘ copy from hybrid to dense subvector where end is not word-aligned overwrote rest of last word
    ∘ dot-product(BitSubvector, Hybrid) broken
    ∘ BitSubvector::word_iterator::operator = not copying _ref._m.full, so _ref._m not always properly initialised
    ∘ When BitSubvector has length == WordTraits::bits and is word-aligned, word_end_reference::mask == 0 while wordBegin () == wordEnd ()
    ∘ BitSubvector::word_iterator::operator + called constructor without passing _shift
    ∘ BLAS1::head(DenseZeroOneVector) not checking back_word ()
  • Create trait for matrices which support writable submatrices -- then GaussJordan can be made more generic
  • Import F4-solver into LinBox and introduce as method for EchelonForm
  • Way to configure intermediate matrix-types used by F4Solver
  • Take attach_block from Splicer and make new appendSubvector in VectorWrapper; write tests for this
  • Similiar with attach_e_i
  • Improvements to BitSubvector, Hybrid subvector:
    ∘ Add support for specifying the start-iterator in a hybrid subvector directly so as to save one binary search on each construction
      ‣ Change attach_block and Splicer accordingly
    ∘ Exploit sentries in HybridVector to reduce cases which need to be checked
  • Rename vector-traits to vector/traits, matrix-traits to matrix/traits
  • Missing specialisations of GF2 dot: hybrid/hybrid, hybrid/sparse, ger (all versions)
  • Missing specialisations for generic operations: trmv (all variants), trsv (Sparse, SparseZeroOne, HybridZeroOne)
  • Sort out header-file-business: order in which header-files are included affects whether the compiler finds certain instantiations and the relationship is really delicate. This needs to be made more robust!
    ∘ Field-header must be included before blas/level* 
    ∘ gf2.h must be included before modular.h
  • Naming-convention: ConstBlah/Blah vs. Blah/MutableBlah?
  • SparseSubvector specialisation to SparseVectorTag is really a specialisation to SparseVector only, since it depends on more than just the interface of std::vector<std::pair<...> >
  • Redo trsv and write trmv (need generic way to make subvectors)
  • Make RandomDenseStream<DenseZeroOne>::get faster by getting whole words at once

Work for HiWi
  • Improvements to build-process:
    ∘ Make the library compile standard instantiations for all non-inline functionality
    ∘ Non-inline stuff goes into new files *.tcc while inline stuff goes into *.h
      ‣ Implementations of Stream::get should go in stream.tcc
      ‣ Contents of gf2.inl should go into gf2.h and (specialisations of streams) to vector/stream-gf2.h, with get-implementation in vector/stream-gf2.tcc
  • Improvements to test-suite
    ∘ Need tests for vectors
    ∘ Improve MatrixDomain tests
      ‣ Add tests for MatrixDomainM4RI, MatrixDomainBLAS, etc.
      	• MatrixDomainBLAS-tests await work on FFLAS
      ‣ More mixtures of matrix-, and vector-formats (need careful review of what is tested)
    ∘ Incorporate tests in F4 to test-suite
      ‣ test-gauss-jordan depends on incorporation of Gauss-Jordan transform into LinBox
    ∘ Enhance tests for HybridVector: offset 0-related cases in SparseSubvector<Hybrid>
    ∘ test-gauss-jordan needs to test more than just GF2-case (!)
    ∘ Move GaussJordan::testFastAddinHybridVector to tests and eliminate RunTests
    ∘ diagIsOne in tr{s|m}{m|v} should be properly tested (true case tested only indirectly at the moment)
    ∘ Consolidate upper, lower triangular variants of trmm, trsm tests to one function
    ∘ Test start_idx, end_idx on dot, gemv
    ∘ Improvements to tests for hybrid-vectors: current tests make no attempt to ensure that the vectors have sufficient gaps (maybe create a new type of VectorStream for this situation)
    ∘ Test for EchelonForm
    ∘ Test for Splicer
    ∘ Meaningful unit-tests for Splicer
    ∘ No direct test for is_zero in test-vector-domain
    ∘ No direct test for BLAS1::permute
    ∘ No direct test for BLAS1::read, BLAS1::write
    ∘ Rename test-vector-domain to test-blas1
    ∘ Split test-matrix-domain into test-blas2 and test-blas3
    ∘ Tests for reduced/non-reduced row-echelon form for GaussJordan, also standard on dense/sparse types
  • API-changes
    ∘ Change interface of inv and div: return bool; true if successful, false otherwise
    ∘ trsv should fail if the input-matrix is not nonsingular upper triangular (or at least with nonzero entries along the diagonal)
    ∘ Figure out archetype/abstract/envelope business
      ‣ Do we need archetype at all (except for documentation)? Maybe merge with abstract
      ‣ Do we need envelope at all?
      ‣ Create matrix archetype to document interfaces
      ‣ Remove redundant documentation from matrices
  • Robustness/safety issues
    ∘ Fix Commentator so that it passes valgrind
    ∘ Valgrind everything else
  • clean up use of inline

Lower priority:
  • Output-improvements to Commentator?
  • Remove some matrix output-formats
  • Create mechanism for "preferred matrix-type" over a given field which can be changed according to available libraries
  • Replace "namespace LinBox" with macro to fix indentation-sillyness
  • Replace __LINBOX_BITVECTOR_WORD_TYPE with a typedef
  • Simplifications to BitSubvectorIterator: move mask-computation to BitSubvector, have iterator in BitSubvector which points to position at which mask is required
  • Move random GF2-streams to new vector/stream-gf2.h
  • Improvements to MatrixDomain
    ∘ Function to read a permutation from stream
    ∘ Move writePermutation to VectorDomain and add a call-through in MatrixDomain?
  • Merge FieldTraits and ModularFieldTraits
  • Rename MatrixTraits::BlackboxTag to something sensible
  • Reorganise MatrixTraits:
    ∘ MatrixCategory (Sparse, Dense)
    ∘ MatrixIteratorCategory (Row, Col, RowCol)
    ∘ MatrixEntryCategory (Element, ZeroOne)
  • Merge BitSubvectorWordAligned into BitVector (maybe using same model as SparseVector)
  • PLUQ-decomposition
  • When type is invalid, tr{s|m}m should throw exception rather than silently doing nothing
  • Add range-parameters start_idx, end_idx to dot and non-specialised gemv
  • Solutions for det, rank
  • Right-hand versions of trsm, trmm

Fuzzy/not sure what to do yet:
  • Eliminate/merge FieldAXPY?
  • Try to consolidate the myriad field/modular-* files, since they are all almost identical

For F4-backend:
  • Make hybrid zero-one matrix more memory-efficient by reducing space-requirements for index-vectors
    ∘ Reuse existing index-vectors
    ∘ Overlay index-vectors with small additional vectors to reflect small changes
    ∘ Need an algorithm which does all of this efficiently
  • Improve matrix-multiplication with hybrid-matrices (!)
    ∘ Way to incorporate M4RI?
    ∘ Way to use Method of 4 Russians for Multiplication?