more on interval BLAS

[David G. Hough at validgh]

Date: Wed, 20 Sep 95 12:31 CDT
From: georgecaboris.mscs.mu.edu (Dr. George F. Corliss  MU MSCS)
Subject: Wuppertal meeting

The pre-Wuppertal meeting to discuss BIAS issues will
be held At the University, Room G 14.34 (building G, level 14),
Monday, September 25, 3:00 -- about 5:00.

The previous discussion is repeated below, followed by
remarks from several others to spark your thinking on these
issues


From: georgecaboris.mscs.mu.edu (Dr. George F. Corliss  MU MSCS)
To: reliable_computingainterval.usl.edu
Subject: Pre-SCAN '95 meeting?
Sender: owner-reliable_computingainterval.usl.edu

If you are coming to SCAN '95 in Wuppertal beginning Sept 26,
I would like to invite you to meet at 3:00 PM Monday, 25 September
(Andreas, can you suggest a location?), the afternoon before the
meeting begins.  The purpose of the meeting is to discuss
standards/cooperation for freely available interval packages.

This call comes from discussions of Corliss and Walter at ICIAM
in Hamburg in July.  Bill Walster has agreed to help chair this
discussion.  One possible outcome would be interval packages
Sun can distribute with their standard distribution tapes as they
are currently doing with Kearfott's INTPAK.

I hope that you are able to come to discuss ways we as a
community can work cooperatively and reduce wheel-reinvention.
If you CAN meet on Monday afternoon, 25 September, please let
me know.  If you know of others interested in participating,
please invite them and pass this message along.


Some of my thoughts:

I was motivated by a paper by Walster, "Stimulating Hardware and
Software Support for Interval Arithmetic" to appear in a volume 
"Applications of Interval Computations," R. B. Kearfott and V. 
Kreinovich, eds., Kluwer.  The volume is presently in production 
at Kluwer, and should appear soon.  Walster's paper caused me to 
reflect on the Basic Linear Algebra Subroutines (BLAS) library.  
Packages for interval arithmetic might follow a similar model.

BLAS level 1 - (floating point) vector-vector operations
BLAS level 2 - (floating point) matrix-vector operations
BLAS level 3 - (floating point) matrix-matrix operations

I proposed:
BIAS level 0 - interval-interval scalar operations
BIAS level 1 - interval vector-vector operations
BIAS level 2 - interval matrix-vector operations
BIAS level 3 - interval matrix-matrix operations

In particular, the Hamburg BIAS package is already well along
with this model.

I think the BLAS people did several things right.  We could
do MUCH worse than to copy from them as much as we can.  It would
be GREAT if we could get one or two of the BLAS people interested
enough to at least serve as advisors to a BIAS effort.

1.  BLAS offer a perfectly portable interface.  That is, if I write
BLAS-calling code, it is perfectly portable across any machine.

2.  BLAS offer ready-to-read, easy-to-port (but sub-optimal) code.
Hence, I can run BLAS-calling code on ANY machine.

3.  BLAS can be made into as machine-specific implemetation as one cares.
Hence, if someone (perhaps the vendor) provides optimized BLAS,
then I get great performance.  The release of at least one machine
optimized implementation along with the portable implementation is
essential to prove the concept of a portable, yet machine-specific
library.

4.  BLAS is a level-ed concept.  Their level 1, 2, and 3 are
mathematically clear and allowed them to release "part" of their
libraries at a time.  We need a level 0 for interval scalar-scalar
operations on which level 1 BIAS routines will build.

5.  BLAS is highly modular.  Individual routines can be developed
at separate, loosely-coupled institutions.

6.  BLAS offer a consistent interface derived from consideration of
tasks needed by client programs, not from consideration of what
some BLAS coder thought was cool.

7.  BLAS is a relatively low-budget operation.  Most of the design
and coding effort was done but a widely distributed set of
researchers as part of their own research programs.

8.  BLAS is freely available (in the portable form).
Vendor-specific implementations can be included in vendors'
libraries.

9.  BLAS published early and often, attracting a lot of attention.

10. BLAS involved the "big guns" of numerical linear algebra so
that new code development in that research area use it.  Hence,
BLAS has become THE standard low-level library interface in that
area.

11. BLAS developed new numerical analysis as it went.  One might
think that a library to those interface specifications was "just" a
coding exercise, but they proved (by a string of publications) that
there remained research to be done.  A BIAS effort can take
advantage of the BLAS research results, shortening our development
time.  We should expect to do some original research along the way,
too.


We should be able to do all the same things for a BIAS library,
PLUS the interval vector-vector, interval matrix-vector and
interval matrix-matrix routines should have exactly (to the extent
possible) the same interfaces as the corresponding BLAS routine.
The BLAS people have even done our interface design work for us :-)

I would like to know more about how the BLAS people coordinated
their distributed development efforts.  E-mail helps.  Meeting at
conferences helps.  Visits of one team member to another helps.
However, it seems that at least a LITTLE closed workshop of
developers meeting from time to time would be essential.  That is
where I was hoping that Sun might be able to take the first lead.

Speed is VERY important.  Good interval algorithms tend to run
roughly 4 times as long as good point algorithms.  That figure
varies A LOT, from < 1 for some global optimization and a few
quadrature problems, to several hundred for some ODEs.  Hence, we
must be able to present ourselves in the most favorable light
possible.  That requires a fast library.

The other issue here is tightness.  A machine-specific library is
likely to be BOTH faster and tighter than a generic library.  A
machine-dependent operation will usually yeild 1 ULP results, while
a portable library will usually yield 2-3 ULP results.  In some
applications, the client software using the portable library will
do additional iterations of some contractive map to overcome the
excess width from its operators.  Hence, the portable algorithm is
slower, as well as the individual portable operations being slower.

George F. Corliss
Dept. Math, Stat, Comp Sci
Marquette University
P.O. Box 1881
Milwaukee, WI  53201-1881  USA
georgecamscs.mu.edu
(414) 288-6599 (office)



=====
>From Eng.Sun.COM!Bill.Walster Fri Sep 15 20:59:56 1995
From: Bill.WalsteraEng.Sun.COM
Date: Fri, 15 Sep 1995 18:59:49 -0700
To: georgecaboris.mscs.mu.edu
Subject: Re: Wuppertal meeting
Cc: Bill.WalsteraEng.Sun.COM


George,

In any case, one thing that would help vendors is to know what kind
of hardware and compiler support are needed.  On the HW side, I
believe we need to provide directed rounding for single, double and
quad with no penalty for switching rounding modes.  Having an interval
standard will help with the compiler support as we will then be sure
we are following standard syntax and semantics.

I also believe your suggestions regarding interval libraries for
important and frequently used routines to be well taken.  I have
guys who would love to work on a Sun version of exactly what you
are suggesting.  We still need to keep making the business case.

I am looking forward to visiting with you again,

Best regards,

Bill
  
======
>From wmai09.math.uni-wuppertal.de!csendes Sat Sep 16 03:06:04 1995
Date: Sat, 16 Sep 95 10:05:52 +0200
From: csendesawmai09.math.uni-wuppertal.de (Tibor Csendes)
To: georgecaboris.mscs.mu.edu
Subject: Re: Pre-SCAN '95 meeting?


Dear George,

thanks for your invitation, I'll be there (wherever it will 
be - I guess somewhere in the campus). My old handcoded Fortran 
subroutines will not help much - but I am ready to help
where I can. I do have some experience with shareware codes 
(we have a modest open library of
optimization codes at an ftp site of our university). 

Yours,

Tibor Csendes

======
>From cma.univie.ac.at!neum Sat Sep 16 07:46:50 1995
Date: Sat, 16 Sep 1995 14:50:38 +0200
From: Arnold Neumaier <neumacma.univie.ac.at>
To: georgecaboris.mscs.mu.edu
Subject: Re:  Pre-SCAN '95 meeting?
Cc: neumacma.univie.ac.at

George,

since I am not at SCAN'95,
here some remarks on your text.

>>We should be able to do all the same things for a BIAS library,
PLUS the interval vector-vector, interval matrix-vector and
interval matrix-matrix routines should have exactly (to the extent
possible) the same interfaces as the corresponding BLAS routine.<<
Not quite; we also need operations real-interval 
and real-real->interval on each level.
Actually this is quite frequent, since good interval code always
uses lots of real calculation which, at some stage, mixes with intervals.
One would have to look at the standard applications to see which
of these operations are frequent.

>>tightness ...  the client software using the portable library will
do additional iterations of some contractive map to overcome the
excess width from its operators<<
No; additional iterations would not help. Lack of tightness will 
result in one or two bits less final accuracy of the bounds, nearly 
independent of applications. For most applications of engineering 
accuracy, this does not matter at all, since the loss of accuracy 
is only a tiny fraction of the interval width. For high accuracy 
applications (where mathematical problems with exact data are being 
solved, ore very illconditioned ones), the software needs anyway a 
component that does multiprecision operations, and intervals only 
for the residuals, and the situation becomes again harmless.
So there is no time penalty in using operations that are not optimally 
tight.

Best wishes,

Arnold


=======
>From magnus.acs.ohio-state.edu!rmoore Sun Sep 17 08:26:27 1995
From: Ramon E Moore <rmooreamagnus.acs.ohio-state.edu>
Subject: Re: Pre-SCAN '95 meeting?
To: georgecaboris.mscs.mu.edu (Dr. George F. Corliss  MU MSCS)
Date: Sun, 17 Sep 1995 09:26:25 -0400 (EDT)


George,

I have to say you guys are doing a bang-up job keeping the ship afloat.

Carry on and the best of luck to all of you.

Ray Moore


======
>From inf.ufrgs.br!diverio Mon Sep 18 13:04:49 1995
Date: Mon, 18 Sep 95 05:36:52 EST
From: diverioainf.ufrgs.br (Tiaraju Asmuz Diverio)
To: georgecaboris.mscs.mu.edu
Subject: Re:  Pre-SCAN '95 meeting?

Dear professor Corliss
I attend to the conference of SCAN 95 in Wuppertal
I am Professor in Federal University of  Brazil - UFRGS
We develone interval libraryin the Cray Y-MP2E, the language that we
use was Fortran 90. This library has 290 routine. Only real rotines
we yet not developed complex module. This library has many
routines vector-vector, matrix-matrix and vector-matrix interval, real 
I will arrive at Wuppertal only in September 26 Tusday. Now I am in Coimbra
portugal. My official addres are in Porto Alegre - RS Brazil

diverioainf.ufrgs.br

I woul like share about this pre-conference after i arrive, it will
be possible. 
m
ay share with you, during the conference. Ok?
See you in SCAN
Prof Tiaraju Diverio
Universidade Federal do Rio grande do SUL
Porto alegre Brazil


=======
>From cs.utk.edu!hammarli Mon Sep 18 08:53:01 1995
Date: Mon, 18 Sep 1995 09:52:58 -0400
From: hammarliacs.utk.edu
To: georgecaboris.mscs.mu.edu
Subject: : Re: Interval BLAS Proposal
Cc: David.HoughaEng.Sun.COM

Dear George,

I received your message about the interval BLAS via David's
numeric-interest mailing. As one of the Level 2 and 3 BLAS authors, as
well as an LAPACK author, I would be happy to act as some sort of
informal advisor to your efforts if that would be useful to you. Of
course, as you know, I am not an expert in interval methods.

By the way, on your point 11, we did not really develop new numerical
analysis as part of the BLAS effort, rather we built on ideas about
algorithms for scalar, vector and parallel shared memory machines by
ourselves and many others. That was important, because we felt that we
understood what was required of the specification for building higher
level applications. Inevitably, we did not get it all right, but I
believe that the LAPACK effort has shown that we did get a lot right.

The LAPACK effort has been where most of the numerical analysis has
been done. (And let me not forget the earlier LINPACK project which
built upon the pioneering work of the Level 1 BLAS.)

Anyway, I certainly support your proposal for a 'BIAS' effort. You
need a small closed group to do the actual work, but as much open
discussion of the ideas as possible so that the community can comment
and feel involved.

Best wishes,

Sven.


=====
>From cam.nist.gov!lozier Mon Sep 18 09:42:28 1995
Date: Mon, 18 Sep 95 10:42:09 EDT
From: lozieracam.nist.gov (Daniel W Lozier)
To: georgecaboris.mscs.mu.edu
Subject: Re: Pre-SCAN '95 meeting?
Cc: lozieracam.nist.gov, boisvertacam.nist.gov, william.mitchellanist.gov

George,
   I like your idea.  The blas have been very influential and have,
as you said, led to further research and more advanced software such
as lapack.  In nailing down the really basic matrix operations by
defining interfaces and providing portable and machine-specific
software, they have undoubtedly led to better software in both libraries
and user-programmed applications.  It is a good model for interval
arithmetic.

Interval arithmetic needs to be more widely recognized as a valuable
computing technique.  I see some evidence that some in the computing
community see a need for reliable computing.  For example, a recent
call for papers for a special issue of the Applied Computational
Electromagnetic Journal (the ACES Journal) included the following:

"Wherever possible, attention should be given to error estimates.  This
is not just a difficult mathematical issue, it is absolutely vital for
all engineering considerations and it is still largely unresolved in
computational electromagnetics.  Modern numerical analysis seems not
to have lived up to its basic premise, because we do not yet possess
useful error estimates."

(The theme of the special issue is "Applied Mathematics: Meeting the
Challenges Pesented by Computational Electromagnetics.")

Regards,
Dan Lozier