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

exact dot product

Dear colleagues,

 

In a mail of May 15, 2013 Vincent Lefevre wrote among others:


And about 11.11.11, "Complete arithmetic, dot product function"
(for 754-conforming types): I completely disagree on it being a
requirement. IMHO, it should not even be normative. P1788 is a
standard on interval arithmetic. I don't see the point of having a
single paragraph on a different arithmetic (which, BTW, would rather
belong to IEEE 754). If the only goal is to have an interval version
of the dot product, then the dot product could be specified like the
other operations, without enforcing an algorithm. 

In general I appreciate Vincent’s mails, but not this one. Nevertheless I am grateful to have it. It gives 
me a chance to answer. There may be others who share his view.

We all know that floating-point arithmetic can easily fail to find the correct answer after only a few 
arithmetic operations. Thus interval arithmetic was invented. It allows computing safe bounds for the 
solution. But these bounds frequently turn out being overly pessimistic. So many sophisticated tools 
and methods have been developed for getting close bounds for the solution. A general, simple and 
most flexible and of these tools is the exact dot product. 

 

I agree that IEEE P1788 is called a standard for interval arithmetic. But I think we would make a big mistake if we would unnecessarily restrict it to the four basic arithmetic operations for real intervals. Techniques for computing close bounds for solutions should also be considered in IEEE P1788.

I am sure that many numerical analysts share this view. See the letter of the IFIP WG 2.5 on Numerical Software to the standard committee IEEE 754 (attachment 1). It requires an exact dot product for the data format double precision. IEEE 754 did not reject this requirement. Their primary goal was a revision of the floating-point standards 754 and 854. In an answer they said: we feel we do not have enough information at this time to make a useful definition of these extensions. We have been considering proposals along these lines for the past 6 years and nothing has so far risen to the level of consensus of any kind.

Thus another standard committee IEEE P1788 was founded. The IFIP Working Group on Numerical Software then sent another letter to IEEE P1788 (attachment 34). It says:
The IFIP Working Group 2.5 on Numerical Software very much appreciates the important work of the IEEE Interval Arithmetic Working Group in the development of a standard for interval arithmetic to support scientific computing with guarantees.
In that regard, WG 2.5 strongly supports inclusion of an exact dot product in the IEEE Standard P1788. The exact dot product is essential for fast long real and long interval arithmetic, as well as for assessing and managing uncertainty in computer arithmetic. It is a fundamental tool for computing with guarantees and can be implemented with very high speed.
We believe that this capability would provide much needed support for verifiable numerical computing, whose easy availability would serve to increase the reliability of scientific computing for many critical applications.

Other scientists also strongly support these requirements. For the International Super Computing Conference 2010 I prepared a poster and a corresponding paper entitled: Very fast and exact accumulation of products, see attachments 3 and 4. The poster got the Research Poster Award ISC'10.

In my book Computer Arithmetic and Validity - Theory, Implementation, and Applications, De Gruyter 2008 and 2013, interval arithmetic is not restricted to the four basic arithmetic operations for intervals over the reals. All arithmetic operations for intervals in the usual product spaces of computation like complex numbers, vectors, or matrices are also provided with the same accuracy requirements as for intervals over the real numbers. It is shown that all arithmetic operations for intervals in the product spaces can be provided if, beyond of conventional floating-point and interval arithmetic, a fast and exact multiply and accumulate operation or, equivalently, an exact scalar product is made available.

With it dynamic precision interval arithmetic can be defined (section 9.7.2). It is also required by the IFIP letter to IEEE 754. It turns out to be a very powerful tool which allows computing close bounds even for extremely ill-conditioned problems. All these applications are very fast. 

The simplest and fastest way for computing a dot product is to compute it exactly. By pipelining it can be computed in the time the processor reads the data, i.e., it comes with utmost speed. No software simulation can compete with a simple and direct hardware solution. The hardware needed for the exact dot product is comparable to that for a fast multiplier by an adder tree accepted years ago and now standard technology of every modern processor. The exact dot product brings the same speed up for accumulations at comparable costs.

Modern computer hardware is very powerful. Arithmetic operations for data or intervals in the usual product spaces which can be performed exactly with very high speed and at low cost should never be done approximately or simulated by slow software.

Of course I know that the standard IEEE P1788 should not require particular hardware. But I think for arranging the standard it is important to know that certain operations can easily be realized by simple and fast hardware.

What in 11.11.11 is called "complete arithmetic", i.e., fast and exact accumulation of products, was a fundamental and powerful operation on many ancient electromechanical calculators. See the upper right corner of the poster. It was the basic operation for iterative refinement or defect correction techniques. This operation was too complicated to be realized in the technology of the early electronic computers. Later it was forgotten. Complete arithmetic just reintroduces this extremely useful operation.

Final remark: The version of DRAFT 7.1 of the standard IEEE P1788 that is shown under Rationale of motion 44 differs in some details from the contents of motion 9. With nearly identical mails of October 11, 2012 and of April 14, 2013 Van Snyder and myself asked for corrections. A final version of DRAFT 7.1 should reflect these.

Best wishes
Ulrich Kulisch

 



-- 
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematik
D-76128 Karlsruhe, Germany
Prof. Ulrich Kulisch

Telefon: +49 721 608-42680
Fax: +49 721 608-46679
E-Mail: ulrich.kulisch@xxxxxxx
www.kit.edu
www.math.kit.edu/ianm2/~kulisch/

KIT - Universität des Landes Baden-Württemberg 
und nationales Großforschungszentrum in der 
Helmholtz-Gesellschaft

Attachment: IFIPWG-IEEE754R.pdf
Description: Adobe PDF document

Attachment: IFIPWG-IEEE-P1788.pdf
Description: Adobe PDF document

Attachment: ISC'10clr.pdf
Description: Adobe PDF document

Attachment: Poster22.pdf
Description: Adobe PDF document