Re: [ublas-dev] Re: [boost] Re: Boost Mathematicians

From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2004-07-05 19:51:04

Hi Michael,

On Jul 5, 2004, at 4:52 PM, Michael Stevens wrote:
> Hi Jeremy,
>
>  Thanks for chipping in on this. I don't think we have conversed 
> before, apart
>  from maybe a few patches I submitted for MTL. Although it would be 
> great for
>  everyone to work on uBLAS I think a revived MTL would also be a good 
> thing.
>  The design of MTL was very influential.

Thanks!

>  I won't comment on the other issues as I have already posted a few 
> thoughts on
>  these matters.
>
>  > >  Mmmh, this open pitfalls concerning A*B*C in performance issues 
> for
>  > >  non experts.
>  >
>  > No, the right way to handle this is to have the expression template
>  > machinery
>  > identify that a temporary is needed, and create one automatically.
>
>  I wonder if you caught the discussion on this about 6 months ago. I 
> would
>  strongly argue that the automatic creation of temporaries in the
>  subexpression context is a bad thing...
>
>  The roles of the expressions we declare (as in declarative 
> programming) is
>  twofold. a) to express the mathematical context b) to express how 
> this should
>  be computed. That is, to be able to express how the expression is to 
> be
>  evaluated. This gives us control over its numerical properties and 
> also of
>  the time and space complexity.
>
>  In principle, uBLAS has a one to one relationship between an 
> expression and
>  how it is evaluated. Simply stated this is based on an element by 
> element
>  evaluation of assignment. There are shortcuts in the case of sparse 
> types but
>  the principle holds.
>
>  An expression A+B+C can be evaluated in this manner trivially.
>  A*B*C can also be evaluated in this manner, although the element by 
> element
>  rule results in an O() that is not what many users expect.
>  To get the O() that users expect we could automagically insert 
> temporaries. I
>  fear this is a tar pit however. What temporary should be chosen? Each 
> of A B
>  or C could be a either dense, sparse, compressed, banded, symmetric or
>  combinations therefore. The type the user expects or is "the best" is 
> not at
>  all clear.

Although automagically inserting temporaries in non-trivial (especially 
since
it must all be done with template meta-programming) I do not think it is
a tar pit. Here is the simply heuristic that I used for MTL 3
to decide where to put temporaries:

1. If an operation needs to read from an argument multiple times,
     evaluate the argument eagerly into a temporary. For example,
     a sparse matrix in compressed row format times the sum
    of two vectors:

    A * (x + y)

   In this case, the (x + y) would be evaluated into a temporary before
   evaluating the multiplication.

2. If an operation writes into its output in multiple passes, then 
perform
    the operation in an eager fashion. For example, the sum
    of a vector and the product of a sparse matrix in compressed column
    format and a vector.

   x + (A * y)

   In this case, the (A * y) would be evaluated into a temporary before
   evaluating the addition.

>
>  I think the only correct solution is to force the user to specify 
> this type.
>  Incidently, the no temporary evaluation should also be an option as 
> in some
>  cases (small sizes) it is desirable. uBLAS currently disallows this 
> to avoid
>  confusing the user. I should be reinstated in some form however.
>
>  All the best,
>        Michael
>
>  --
>  ___________________________________
>  Michael Stevens Systems Engineering
>
>  34128 Kassel, Germany
>  Phone/Fax: [phone]
>
>  Navigation Systems, Estimation  and
>                   Bayesian Filtering
>      http://bayesclasses.sf.net
>  ___________________________________
>
>
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________