Re: exact dot product

[Ulrich Kulisch <ulrich.kulisch@xxxxxxx>]

Baker,

"Complete arithmetic" may appear as something that is new. The technology, however, is not new at all. It was already available on old calculators. See the right upper corner of the poster. In the XSC-languages the format was called "dotprecision". You call it the "long accumulator", and in the paper [5] on the poster something very similar is called "staggered prercision" which, if I remember it correctly goes back to Hans Stetter. The wording "complete arithmetic" was suggested by Neville Holmes (Computers and People, John Wiley, 2006) a very experienced computer science journalist and long term systems engineer at IBM. I mention him in the preface of my book and in the foreword to the second edition.

There are two things that should not be confused:
a) the exact dot product and
b) a correctly or faithfully rounded dot product.

From a) follows b) easily. The opposite is not true. So the number of applications of a) is naturally larger than that of b). The IFIP letters to IEEE 754 and to IEEE P1788 require an exact dot product. It is indeed an essential engredient of verified computing.

Several partcular applications of the exact dot product are listed in the paper: "Very fast and exact accumulation of products" which was attached to my mail of May 18, 2013. See also the poster and my book.

The process of iterative refinement or defect correction, for instance, is composed of scalar products. If these are computed exactly a verified solution of a linear system can be computed even in extremely ill-conditioned cases, where the Krawczyk-operator fails to find a verified solution, by Rump's method. Another very powerful application is dynamic precision or long real interval arithmetic. With it the result of practically every arithmetic _expression_ can be guaranteed to a number of correct digits.

In numerical analysis the dot product is ubiquetous. 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 procesor needs to read the data, i.e., it comes with utmost speed. Any method like b) that just computes an approximation also has to consider the relative values of the summands. This results in a more complicated method. Complete arithmetic uses a data format "complete". You call it a "long accumulator". The result of complete arithmetic is always exact; it is complete, not truncated. Not a single bit is lost. A variable of type complete is a fixed-point word wide enough to allow exact accumulation (continued  summation) of floating-point numbers and of simple products of such numbers. If register space for the complete format is available complete arithmetic is very fast. The arithmetic needed to perform complete arithmetic is not much different from that available in a conventional CPU. In the case of the IEEE double precision format a complete register consists of about 1/2 K bytes. Its length is independent of the number of summands that are to be added. It can be kept in main memory, in cache memory, or ideally in register memory.

Best wishes
Ulrich


Am 21.05.2013 03:57, schrieb Ralph Baker Kearfott:

Dan (and P-1788),

If I may summarize (and Ulrich can correct me if I am wrong),
"complete arithmetic" Involves using a "long accumulator"
(something like 1000 bits for double precision), doing the
summation (e.g. for the dot product, but also for other operations)
in the long accumulator, then rounding.  However, there are
other ways of obtaining a correctly rounded (or the slightly
less stringent faithfully rounded) dot product, and I am
hoping we can clarify exactly what the intent of the position
from motion 29 is in this regard.

Baker

On 05/20/2013 01:19 PM, Dan Zuras Intervals wrote:

Date: Sun, 19 May 2013 16:37:48 -0500
From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxxx>
To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
CC: Ulrich Kulisch <ulrich.kulisch@xxxxxxx>, stds-1788@xxxxxxxxxxxxxxxxx
Subject: Re: exact dot product

Dan (and P-1788),

Was complete arithmetic (in addition to exact dot
product) also discussed in 754?

Baker

	Baker,

	I must confess I am not quite sure what you mean by "complete
	arithmetic" in this context.  But if it is an exact arithmetic
	or an arithmetic with an exact part & a smaller unknown part,
	then YES, it was discussed many times & in many different contexts.

	Also, exact dot product in the context of exact products together
	with correct sums which are exact enough to round correctly all
	the time, these were discussed at length.  Ulrich needed them for
	his work & we were willing to provide them.

	(Actually, in the discussion it often came up that someone wanted
	NOT to provide them from time to time due to their difficulty.
	But eventually a paper was published that put a bound on the extra
	precision needed which pretty much killed the objection.  Alas,
	the paper hit the streets too late for us to change the text of
	the 754 standard.  It will happen to you too in some context or
	another.  Don't be in too much of a hurry.)

	This notion of "complete arithmetic" was also often discussed in
	the context of intervals.  The notion was to compare two numbers
	by having an exact part & a much smaller interval part such that
	the comparison was clear once you subtracted out the exact parts.
	That is, either it was away from zero or not by looking at what
	amounted to only the interval parts.  It was necessary to carry
	out such a comparison by having either exact arithmetic or some
	sort of arithmetic that accumulated its error in the interval
	part.  It was the only way to decide the answer.

	Does this answer your "complete arithmetic" questions?

					Dan

-- 
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