Glas List: [glas] Diploma/Master Thesis about safe scalar products and optimized linear algebra expressions

From: Andreas Pokorny (andreas.pokorny_at_[hidden])
Date: 2005-02-21 15:30:40

Hi, 
I plan to write my diploma (german master) thesis in the field of 
generic/meta programing  and linear algebra. My professor wants 
to see a safe scalar product implemented using expression templates. 
First I evaluated the design of boost::ublas, and noticed that adding
that feature in a comfortable way, means either reimplementing the
expressions or redesigning the library. 
  Reimplement the scalar expressions of the library, was no option,
since that would imply that the user only uses one implementation at a
time. I thought it should be possible to have some control over the
evaluation process. 
  So redesigning makes more sense to me. So I currently think about
an alternative expression evaluation system. The current planing state
looks like that, (expressed in a few lines ) 

template <typename LeftExpression, typename RightExpression>
expression_type<      // the expression holder, operations are defined 
                      // on variants of that template, 
                      // maybe will be split up into the "result_type"
                      // like scalar, vector, matrix, tensor

  choose_optimizer<    // The expressions (and containers) are
   LeftExpression,     // decorated with an optimizer that transforms
   RightExpression     // expression trees, similar to tree analyzers in
                       // compiler theory. 
   >::type::optimize<     // optimize might yield expression types that use special 
                          // vector instructions, e.g. implemented using
                          // gccs builtin function or assembler, 
                          // thus replaces plain expressions with
                          // system/cpu specifc instructions
                          // or maybe expression types that use a certain library binding
   
     get_expresion_system< // the expression system is also stored in
                           // expression types.
       LeftExpression,     
       RightExpression
       >::type::add<       // e.g. it might be possible to implement a safe scalar product 
         LeftExpression,   // in the expression system, which avoids cancelation of summands 
                           // due to divergent floating point exponents  
         RightExpression
         >::type
     >
  >::type  
 >
operator + ( expression_type<LeftExpression> const& left, expression_type<RightExpression> const& const)

The final responsibility between the expression and the optimization system is not yet clear,
maybe both things can be merged into one... 

But currently it is intended in this way:
The special variants of the expression system ( which could derive from a different variant) 
could hide parts of the expression from being overridden by the optimization system by defining 
new types, types that the optimization system does not know. 

The optimization system instead tries to replace known expressions with 
optimized expressions. It could for example replace combined expressions
like add<mul<Matrix,Vector>, Vector > using an expression that
computes the scalar product of a matrix row with the vector and the
addition to the third parameter, in a single step.. 

What do you think so far? 

There is no code yet, my design goals are:
 * extensible expression system, the user should be able to add features
   or activate compiler/cpu/system extensions
 * allow binding of other libraries 

I havent thought about the containers yet... 

Regards 
Andreas Pokorny