wiki:MatrixDesign
Last modified 3 years ago

New design for the matrices in LinBox v2.0

The matrices in LinBox can be of 3 types: BlackBox, SparseMatrix, DenseMatrix. [bds: BlackBox is a Concept (i.e. template parameter), SparseMatrix and DenseMatrix are specific classes. Here I'm proposing 2 concepts, Blackbox and Matrix (much different than current Matrix), and two distinguished classes (SparseMatrix and DenseMatrix). Does this violate the thought behind the '3 types' statement above?]

Their main methods are the following:

Concept Blackbox:

  • BBClass(), default constructor forbidden, is private. (?)
  • BBClass(F), constructor from a field creates 0 by 0 matrix.
  • BBClass(const BBClass& B), copy constructor makes a deep (completely independent) copy.
  • operator=, assignment operator makes a deep copy.
  • ~BBClass(), destructor frees all mem (including vectors passed by reference at construction time if they were just used by the BB).
  • apply(v, u)
  • applyTranspose(v, u)
  • field()
  • rowdim()
  • coldim()
  • rebind() for building modular images
  • read() from a stream or file name. Use parameter to build a matrix stream and get matrix from that.
  • write() to a stream or file name, in (extended) matrix market format.
  • random(), random(m,n)

Concept Matrix is about the ability to efficiently access individual entries, including inserting them during matrix construction time.

  • MatClass(m, n), construct m by n shell for further init. Should be the zero matrix if that is in the class. Some classes may require m == n.
  • getEntry(i,j)
  • refEntry(i,j)
  • setEntry(i,j, v) A.refEntry(i,j) = v

Question: Do we allow BBs that can't accept assignment to every i,j position to meet the matrix concept partially? For instance Diagonal could support Element & refEntry(i,j), throwing an error when i != j, but const Element & getEntry(i,j) is ok.

Raw iterators, rawBegin(), rawEnd(). This idea has limited and unessential uses so far. It's purpose is superceded by rebind() [ and current uses of raw iterators in rebind()'s can be used or rewritten, but there is no genericity about this, so no need for raw iterators in a general Matrix concept.] Let's abandon rawIterators as a generic thing.

Currently, Matrix is a container concept with template parameter Element, whereas Blackbox-es have template parameter Field. I'm fine with keeping this, but let's call this concept MatrixContainer in this discussion. Right now, I'd say the idea is that blackboxes which derive from MatrixContainer are precisely those on which eliminations can be used. I am fine with that but also would consider a Matrix concept having Field template parameter and supporting LQUP. This concept could take over the name Matrix and the current matrix could morph to MatrixContainer. Alternatively, my Matrix concept, a Blackbox extension concept, could be named Eliminable or Factorable or some such. There will be at least one Dense type and several Sparse types meeting this concept.

Class SparseMatrix: extends the Matrix concept and is the `default' sparse matrix representation. It has a special place in MatrixDomain(s) and other places. In particular, sparse elimination is supported on it.

  • rowBegin(), rowEnd() (sparse row iterators)
  • colBegin(), colEnd() (sparse col iterators)

Class DenseMatrix: extends the Matrix concept and is the `default' dense matrix representation. It has a special place in MatrixDomain(s), fflas, and other places. It is the previous BlasBlackbox, i.e. the rep is one rowDim*colDim array in row major order and via its stride can represent a block (contiguous in rows and cols) within a larger DenseMatrix.

  • rowBegin(), rowEnd() (dense row iterators)
  • colBegin(), colEnd() (dense col iterators)
  • getPtr()
  • getStride() between rows

There will be other classes representing sparse and dense matrices, for instance zero-one matrices, partially out of core and distributed matrices, etc. I do not expect much genericity regarding algorithms using these various representations, however, so no generalizing concepts are proposed.

Questions:

  • name for the dense matrices: Matrix or DenseMatrix ? Ans: DenseMatrix
  • How to recognize the type of matrix given to a solution?
    • Overload of parameter for SparseMatrix and DenseMatrix, template for BlackBox. -> simpler code, less template/Traits, better readability
    • template for everyone + Traits -> uniformize the behaviour with template parameters, but heavier
    • I don't understand the choice intended between the above two items. Right now we have a trait for the fields, DomainCategory, to help the solutions dispatch appropriately and we have the methods. It's true that we will also want traits for blackboxes in some solutions. Let's go ahead and do it that way. [bds: I've just reworked getentry.h and trace.h, using a local blackbox trait to handle the special cases.] We can make a special case for specific classes DenseMatrix and SparseMatrix without using a trait. I don't want anything that requires the user to deal with a different interface just because her matrix is a DenseMatrix or SparseMatrix. (bds 2008Aug1)

  • how far should matrices inherit from each other? The choice of using template instantiations makes class hierarchy useless for type checking.
    • no inheritance at all (bds: this gets my vote. Inheritance does not mix well with the templates.)
    • BlackBox SparseMatrix -> DenseMatrix
    • BlackBox -> SparseMatrix -> DenseMatrix
  • Here is something about the reader/writer design.
    • each blackbox read(istream&) should build a MatrixStream on the istream and use the MatrixStream to read in the matrix, thus getting the benefit of accepting numerous file formats in one definition of read().
    • We have never settled on output formats, generally writing sms or dense formats. Attempts at MathML formatting have faded away. I now suggest we write (by default) in MatrixMarket  http://math.nist.gov/MatrixMarket/ format (and we can make extensions thereof) From that we get some compatibility with others and we get a header in which we can write any sort of metadata about the matrix that is useful. For starters, we can make MatrixStream treat lines beginning with '%' as comments.
  • Arguably, getEntry() should be a part of the blackbox interface. It is the settable entry that distinguishes the matrix types from blackboxes.
  • It would also be possible to say that having LQUP is part of the !Matrix category.
  • probably the RowIterator and ColIterator can be part of the !Matrix concept. But I'm questioning how much useful genericity is based on them, as block methods come to the fore.