Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: the "set paradigm" is harmful

On Thu, 12 Feb 2009 17:15:58 -0100, Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx> wrote: 


Siegfried M. Rump schrieb:


I understand that in Arnold's applications wide intervals often
occur. So he cannot accept any overestimation.
In my applications wide intervals occur, but not that frequent.
However, large matrices occur. Multiplication of interval matrices
of large dimension in realistic time needs mid-rad arithmetic:


n=500; A=midrad(randn(n),1e-3); B=midrad(randn(n),1e-3);

 intvalinit('SharpIVmult'); tic, A*B; toc,
===> Slow but sharp interval matrix multiplication in use
Elapsed time is 77.518951 seconds.
 intvalinit('FastIVmult'); tic, A*B; toc
===> Fast interval matrix multiplication in use (maximum overestimation
        maximally factor 1.5 in radius)
Elapsed time is 1.418354 seconds.
 The reason is first that matrix mid-rad IV-multiplication can use BLAS
routines. Second it needs only 2 times to switch the rounding mode
compared to (at best) n^2 times for inf-sup multiplication.


This only shows an an inefficient implementation of the exact
matrix-matrix multiply. One can use BLAS and gets by with two
rounding mode changes if one uses X*Y = sum_j X(:,j)*Y(j,:) and first
computes all upper bounds, and then all lower bounds.

I'd be interested in how this compares in timing with the above.


Arnold Neumaier



This IS used in INTLAB because it is the fastest way using Matlab.
However, these are rank-1 updates, so cache misses slow down the
computation. Moreover, in total 8 matrix multiplications are
necessary whereas mid-rad arithmetic needs only 4.

In Profil our method to reduce n^3 to n^2 switching of the rounding
mode is used. The advantage is that dot products can be used and
cache misses are avoided. The result is slightly more narrow at the
price of much slower computing time.

Siegfried M. Rump

--
=====================================================
Prof. Dr. Siegfried M. Rump
Institute for Reliable Computing
Hamburg University of Technology
Schwarzenbergstr. 95
21071 Hamburg
Germany
phone  +49 40 42878 3027
fax    +49 40 42878 2489
http://www.ti3.tu-harburg.de

and

Visiting Professor at Waseda University
Faculty of Science and Engineering
Shinjuku Lambdax Bldg. 902
2-4-12 Okubo, Shinjuku-ku
Tokyo 169-0072
Japan
phone/fax in Japan  +81 3 5286 3414