Todo

From Eigen
Revision as of 14:46, 16 April 2008 by Bjacob (Talk | contribs)

Jump to: navigation, search

Core module

This module is essentially complete and working, but needs improvement in these areas:

  • Vectorization
** Add AltiVec support.
** Fix compilation errors with complex numbers (probably just disable vectorization in this case). In particular, ensure the tests compile and succeed with vectorization turned on.
** Add ability for certain operations to view a matrix op as a vector op. Needed e.g. to vectorize ops on 2x2 matrices.
** Evaluate adding vectorization support to (certain) block expressions. Related to adding support for specifying startRow/startCol parameters as template parameters.
** Add vectorization support to dynamic-size matrices. Here the good approach is not really to align the data array on 16-byte boundary (that might help sometimes, but typically we'll be working with dynamic block expressions not preserving the alignment). The better approach is probably to allow arbitrary operations to vectorize the part of them that can be vectorized. That would consist in doing with non-vectorized instructions the operations near unaligned boundaries, and vectorize what's in the middle (between aligned boundaries). That means runtime checks, but looping in dynamic-sized objects means conditional branching anyway.
  • Parallelization
- Ensure that large cwise-ops scale well (this should be easy, but currently doesn't give good results).
- Parallelize redux and visitor.
- Keep in mind that we want to prevent nested parallelization. Fortunately that shouldn't happen as costly xprs are evaluated when nested into other xprs. But there is room for improvement to make us more solid against that.
- Is it worth implementing divide-and-conquer in matrix product and inversion? Besides allowing for better parallelization, this is also more cache-friendly and results in fewer ops for large matrices. But this might be overkill for us.
  • Misc Features
- We need an efficient way of computing m * m.adjoint() and m.adjoint() * m. Can this be done cleanly? I am afraid we'll have to re-write at least a separate meta-unroller for this one. So maybe make a new Xpr for that while we're at it.
- I don't think anymore we need masks for copying upper/lower triangles. Probably too much hassle. Was mostly useful in fixed-size cases, but for them algorithms which might use that are often superseded by special algorithms for small sizes (such as cofactors for computing an inverse).
- Evaluate adding CwiseNullaryOp, grouping Zero, Ones, Identity, Random.

LU module

  • Inversion: it's done, but more work is needed:
- fixed-size 4x4: either merge the vectorization code by Markos (hopefully making it work with SSE as well as AltiVec) or improve Eigen's generic vectorization code enough to achieve comparable performance.
- general case: evaluate doing at least one step of divide-and-conquer as in the size 4 case, to reduce overall complexity and improve parallelizability.
  • Determinant: only fixed-size <= 4 is done, the general case remains to do. Perhaps make it just use a LU decomposition, as large determinants are seldom used anyway.
  • LU decomposition: to do. Should have optimized paths for fixed-size <= 4. Very important, as this will be our primary device for all exact solving.
- provide isInvertible(), inverse(), determinant(). It's not redundant to have it also here. Once the LU decomposition is computed these are much faster to compute.
- provide rank(), kernelBasis(), imageBasis(), someAntecedent(vector).

QR module

To do. Should provide QR decomposition, eigenvalues, spectral radius, operator norm, operator exponential and maybe more operator calculus by applying a cwiseUnaryOp to the eigenvalues vector.

SVD module

To do. Should provide SVD decomposition, pseudoinverse, what the vision folks need, and least squares / linear regression.

- Maybe Gram-Schmidt goes here? It's really similar to SVD.

Geometry module

  • Projective geometry / homographies: i'm (bjacob) starting to have precise ideas about this, so leave that to me.
  • Rotation matrices: reuse Eigen 1 code.
  • Quaternions: evaluate reusing Tackat's code in Marble.
  • Need a fixed-size Gram-Schmidt here, so it's not clear whether it belongs here or in SVD. Is this a case for having it in a separate module?

Unit-tests

  • Update them to cover all of the API and add tests for bad bugs we had in the past, such as the sizeof bug.
  • By the way add tests to check that fixed-size object really don't cause mallocs.
  • Get rid of QTestLib, and by the way remove the QtCore dependency.
  • Split tests into many small executables, using CTest to run them. Might even allow us to use -O3 -g3 for compiling, getting decent speed. Currently that causes g++ to use too much memory, especially with >1 jobs.

Documentation

  • Update massively: it's out of date
  • Fix doxygen issues, such as the groups in MatrixBase (as determined by \name) appearing in random order.
  • Write special pages on certain topics, illustrate them with examples:
- Compiler support/options
- Vectorization
- Parallelization
- Fixed-size matrices/vectors
-- in particular, usage with OpenGL
- Dynamic-size matrices/vectors