Re: uBLAS Matrix Multiplication

From: alexei_novakov (alexei_novakov_at_[hidden])
Date: 2002-11-10 17:29:49

--- In Boost-Users_at_y..., "jhrwalter" <jhr.walter_at_t...> wrote:
> --- In Boost-Users_at_y..., John Lloyd <yg-boost-users_at_m...> wrote:
> > Hickman, Greg wrote:
> > 
> > > Why isn't there an overloaded
> > > 
> > > matrix_expression
> > > operator* (const matrix_expression&, const matrix_expression&);
> > > 
> > > for peforming matrix multiplication?
> > > 
> > > Greg Hickman
> > > 
> > > Info: <http://www.boost.org>
> > > Wiki: <http://www.crystalclearsoftware.com/cgi-
> bin/boost_wiki/wiki.pl>
> > > Unsubscribe: <mailto:boost-users-unsubscribe_at_y...>
> > >  
> > > 
> > > Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/
> > 
> > I think it has something to do with the fact that expression 
> templates can 
> > be very inefficient for certain chained operations, e.g., A * B * 
> v, where 
> > A and B are matrices and v is a vector.
> > 
> > Suppose you have a  matrix expression like A = B * C * D.  Using 
> expression 
> > templates, this could result in an order n^5 time complexity as 
> opposed to 
> > order n^3 complexity.
> 
> Exactly. I believe the theoretically more important signature is
> prod<matrix_type> (A, B), although prod (A, B) will be more 
> frequently used practically (BTW: the complexity of prod (A, B) (i, 
> j) is O(n) as opposed to O(n^3) for prod<matrix_type> (A, B) (i, 
j)).
> 
> Best regards
> 
> Joerg

Here are couple of thoughts:
1) matrix-matrix multiplication and matrix-vector multiplication are 
ones of most used operators in matrix computations (especially 
second), if these are not presented the value of expression framework 
itself becomes questionable.
2) To avoid extra computational compexity temporaries can be used. In 
some cases temporaries are presented in expressions already, like:
A = B * C;
Matrix A can be used as temporary. More complex expressions like:
A = B * C * D;
will require additional temp matrix.
3) To minimize performance penalty template specialization can be 
used. For example:
  matrix_matrix_prod<sparse_matrix_type, sparse_matrix_type> {
   ...
  };
  matrix_matrix_prod<sparse_matrix_type, dence_matrix_type> {
   ...
  };
  etc.

Regards.

Alexei Novakov