From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 1 16:35:50 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id QAA23594
for reliable_computing-outgoing; Mon, 1 Nov 1999 16:35:50 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id QAA23589
for ; Mon, 1 Nov 1999 16:35:38 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id PAA04837;
Mon, 1 Nov 1999 15:35:26 -0700 (MST)
Message-Id: <199911012235.PAA04837 [at] cs [dot] utep.edu>
Date: Mon, 1 Nov 1999 15:35:25 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: open positions
To: reliable_computing [at] interval [dot] usl.edu
Cc: vladik [at] cs [dot] utep.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: i6+FjpW256VJUXv/NtrQng==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Friends,
As of today, we have a new chairman, and he encourages us to send our ad to
mailing lists to help recruit people from the areas in which we are doing
research already. I am therefore sending this ad to the interval computations
mailing list.
Vladik
The University of Texas at El Paso
Department of Computer Science
The Department of Computer Science of the University of Texas at El
Paso invites applications for at least two tenure-track faculty
positions at all ranks to begin in the Fall of 2000. We value
excellence in research and education, our environment of collegiality,
faculty collaboration across a wide range of interests, and involvement
with students outside the classroom. We seek colleagues who share
these values and who have a strong commitment to both education
and research, can collaborate with other faculty, can build a
strong research program, and enjoy working in a
culturally diverse community.
The Department of Computer Science is part of UTEP's College of
Engineering. We offer BS and MS degrees in computer science and, with
the Department of Electrical and Computer Engineering, a Ph.D. degree
in Computer Engineering. We have an internationally distinguished
record of research, and our teaching program is a nationally recognized
model of excellence.
UTEP is a university of 15,000 students. Our campus, located close to
where the Rocky Mountains meet the Rio Grande, echoes the beauty of the
surrounding high desert. El Paso, a dynamic community of 700,000
people, is a major meeting point between the United States and Latin
America.
We will consider applications in all areas of computer science.
Candidates must hold a Ph.D. in computer science or a closely related
field. Send a curriculum vitae, a list of publications, a statement of
research and teaching interests, and the names of at least four
references to:
Faculty Recruiting Committee,
Department of Computer Science,
University of Texas at El Paso,
El Paso, TX 79968
Information about the department is available at
http://www.cs.utep.edu. Send e-mail inquiries to
recruiting [at] cs [dot] utep.edu.
The University of Texas at El Paso does not discriminate on the basis
of race, color, national origin, sex, religion, age, sexual orientation
or disability in employment or the provision of services.
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:01:37 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA01821
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:01:36 -0600 (CST)
Received: from kula.mcmaster.ca (IDENT:ned@[130.113.68.86])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA01816
for ; Wed, 3 Nov 1999 10:01:29 -0600 (CST)
Received: (from ned@localhost)
by kula.mcmaster.ca (8.9.3/8.9.3) id MAA01148;
Wed, 3 Nov 1999 12:06:40 -0500
Date: Wed, 3 Nov 1999 12:06:40 -0500
Message-Id: <199911031706.MAA01148 [at] kula [dot] mcmaster.ca>
From:
To: reliable_computing [at] interval [dot] usl.edu
Subject: matrix inverse
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Colleagues,
I have to find an answer to the following question.
Suppose that an NxN matrix A is very ill-conditioned. Is it
possible to compute tight bounds (enclosure) for the inverse of A?
Intuitively, it should not be possible. However, it is not obvious to me
how to prove it.
If you have an answer to the above question, can you also point to some
references?
Regards,
Ned
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:24:01 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA02150
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:24:01 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA02145
for ; Wed, 3 Nov 1999 10:23:58 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id KAA01601;
Wed, 3 Nov 1999 10:23:48 -0600 (CST)
Message-Id: <2.2.32.19991103162447.006e5844 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 03 Nov 1999 10:24:47 -0600
To: , reliable_computing [at] interval [dot] usl.edu
From: "R. Baker Kearfott"
Subject: Re: matrix inverse
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Ned,
Kulisch et al may tell you to use an accurate dot product.
Demmel may ask you how it is ill-conditioned. For that matter, so
may Alefeld and Mayer. In particular, if I recall correctly, dependencies
among the entries (or if "random" errors in the entries have some
pattern) can sometimes be exploited.
For general matrices, I've found the formulas in Golub and van Loan's
"Matrix Computations" (latest edition) to be useful, both for general
insight and as an aid to interval analysis. Thumbing through there may
give you the answer you seek.
Otherwise, I'll encourage some of the people I cited above and others
to reply.
Best regards,
Baker
At 12:06 PM 11/3/99 -0500, nedialk [at] mcmaster [dot] ca wrote:
>
>
>Dear Colleagues,
>
> I have to find an answer to the following question.
>
> Suppose that an NxN matrix A is very ill-conditioned. Is it
>possible to compute tight bounds (enclosure) for the inverse of A?
>
> Intuitively, it should not be possible. However, it is not obvious to me
>how to prove it.
> If you have an answer to the above question, can you also point to some
>references?
>
> Regards,
> Ned
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:36:12 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA02404
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:36:12 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA02397
for ; Wed, 3 Nov 1999 10:35:57 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id JAA13661;
Wed, 3 Nov 1999 09:35:26 -0700 (MST)
Message-Id: <199911031635.JAA13661 [at] cs [dot] utep.edu>
Date: Wed, 3 Nov 1999 09:35:25 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: Re: matrix inverse
To: nedialk [at] mcmaster [dot] ca
Cc: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: sF1UbaLAe9T2Ko7QqrXRFg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Ned,
Probably you need to make a question more specific.
If we just have a matrix A which is not an interval matrix, but which has all
the numbers given precisely, e.g., as rational numbers, then we can simply
use rationl number arithmetic to compute not just the bounds but actually the
exact values of all components of the inverse matrix. For such exact
computations, it does not matter whether the matrix is ill-conditioned or not.
Of course, if we are interested later in getting binary-rational bounds, we can
easily translate the exact rational values into binary-rational bounds.
Arithmetic of rational numbers is a natural excercise for students of our Intro
to CS class, and it is also present in many packages (I believe Mathematica has
it).
Fast algorithms for exact matrix inversions are described, e.g., in Section
31.5 of the textbook Th. A. Cormen, C. E. Leiserson, and R. L. Rivest,
Introduction to Algotithms, MIT Press, 1994.
When I was working at the Institute of Electrical Measuring Instruments in
Russia, we use Mir computer (not to confused with Mir space station :-)) which
had a similar rational arithmetic capability to compute the exact inverses of
highly ill-defined matrices such as Hilbert matrix etc. (For Hilbert matrix, it
was a test, because the analytical expression for the inverse is known).
Vladik
> Date: Wed, 3 Nov 1999 12:06:40 -0500
> From:
> To: reliable_computing [at] interval [dot] usl.edu
> Subject: matrix inverse
>
>
>
> Dear Colleagues,
>
> I have to find an answer to the following question.
>
> Suppose that an NxN matrix A is very ill-conditioned. Is it
> possible to compute tight bounds (enclosure) for the inverse of A?
>
> Intuitively, it should not be possible. However, it is not obvious to me
> how to prove it.
> If you have an answer to the above question, can you also point to some
> references?
>
> Regards,
> Ned
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:40:00 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA02551
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:39:59 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA02533
for ; Wed, 3 Nov 1999 10:39:39 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id JAA13676;
Wed, 3 Nov 1999 09:39:31 -0700 (MST)
Message-Id: <199911031639.JAA13676 [at] cs [dot] utep.edu>
Date: Wed, 3 Nov 1999 09:39:30 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: Re: matrix inverse
To: reliable_computing [at] interval [dot] usl.edu, nedialk [at] mcmaster [dot] ca
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: hXYPXIGeKKqkTMHOTWnelg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
P.S. For interval matrices A, a possible answer to your question on proving
impossibility is contained in a recent paper
Computing Exact Bounds on Elements of an Inverse Interval Matrix is
NP-Hard
by Gregory E. Coxson
137-142
Reliable Computing. - 1999. - Vol. 5, No. 2.
> Date: Wed, 3 Nov 1999 12:06:40 -0500
> From:
> To: reliable_computing [at] interval [dot] usl.edu
> Subject: matrix inverse
>
>
>
> Dear Colleagues,
>
> I have to find an answer to the following question.
>
> Suppose that an NxN matrix A is very ill-conditioned. Is it
> possible to compute tight bounds (enclosure) for the inverse of A?
>
> Intuitively, it should not be possible. However, it is not obvious to me
> how to prove it.
> If you have an answer to the above question, can you also point to some
> references?
>
> Regards,
> Ned
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:45:38 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA02861
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:45:38 -0600 (CST)
Received: from mcmail.cis.McMaster.CA (nedialk [at] mcmail [dot] CIS.McMaster.CA [130.113.64.66])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA02853
for ; Wed, 3 Nov 1999 10:45:33 -0600 (CST)
Received: from localhost (nedialk@localhost)
by mcmail.cis.McMaster.CA with SMTP id LAA00092;
Wed, 3 Nov 1999 11:45:01 -0500 (EST)
Date: Wed, 3 Nov 1999 11:43:56 -0500 (EST)
From: Ned Nedialkov
To: vladik
cc: nedialk [at] mcmaster [dot] ca, reliable_computing [at] interval [dot] usl.edu
Subject: Re: matrix inverse
In-Reply-To: <199911031635.JAA13661 [at] cs [dot] utep.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
On Wed, 3 Nov 1999, vladik wrote:
> Dear Ned,
>
> Probably you need to make a question more specific.
>
> If we just have a matrix A which is not an interval matrix, but which has all
> the numbers given precisely, e.g., as rational numbers
I would like the entries of A to be floating-point numbers and perform all
the computations in interval arithmetic, where the bounds are
floating-point numbers.
Ned
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 10:57:32 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA03298
for reliable_computing-outgoing; Wed, 3 Nov 1999 10:57:32 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA03293
for ; Wed, 3 Nov 1999 10:57:29 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id KAA02367;
Wed, 3 Nov 1999 10:57:22 -0600 (CST)
Message-Id: <2.2.32.19991103165821.0072b7b8 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 03 Nov 1999 10:58:21 -0600
To: Ned Nedialkov
From: "R. Baker Kearfott"
Subject: Re: matrix inverse
Cc: reliable_computing [at] interval [dot] usl.edu
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Do you assume the floating-point entries are exact to begin with?
Baker
At 11:43 AM 11/3/99 -0500, Ned Nedialkov wrote:
>
>
>On Wed, 3 Nov 1999, vladik wrote:
>
>> Dear Ned,
>>
>> Probably you need to make a question more specific.
>>
>> If we just have a matrix A which is not an interval matrix, but which has all
>> the numbers given precisely, e.g., as rational numbers
>
>I would like the entries of A to be floating-point numbers and perform all
>the computations in interval arithmetic, where the bounds are
>floating-point numbers.
>
>Ned
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 11:18:09 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA03794
for reliable_computing-outgoing; Wed, 3 Nov 1999 11:18:08 -0600 (CST)
Received: from mcmail.cis.McMaster.CA (nedialk [at] mcmail [dot] CIS.McMaster.CA [130.113.64.66])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA03789
for ; Wed, 3 Nov 1999 11:18:05 -0600 (CST)
Received: from localhost (nedialk@localhost)
by mcmail.cis.McMaster.CA with SMTP id MAA17388;
Wed, 3 Nov 1999 12:17:56 -0500 (EST)
Date: Wed, 3 Nov 1999 12:17:56 -0500 (EST)
From: Ned Nedialkov
To: "R. Baker Kearfott"
cc: reliable_computing [at] interval [dot] usl.edu
Subject: Re: matrix inverse
In-Reply-To: <2.2.32.19991103165821.0072b7b8 [at] pop [dot] usl.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
On Wed, 3 Nov 1999, R. Baker Kearfott wrote:
> Do you assume the floating-point entries are exact to begin with?
>
Yes.
Ned
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 11:26:06 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA04046
for reliable_computing-outgoing; Wed, 3 Nov 1999 11:26:05 -0600 (CST)
Received: from mailgate.rz.uni-karlsruhe.de (exim [at] mailgate [dot] rz.uni-karlsruhe.de [129.13.64.97])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA04039
for ; Wed, 3 Nov 1999 11:26:00 -0600 (CST)
Received: from iamm17.iamm (iamm17.mathematik.uni-karlsruhe.de [129.13.114.157])
by mailgate.rz.uni-karlsruhe.de with smtp (Exim 3.02 #2)
id 11j4A8-0006N3-00; Wed, 03 Nov 1999 18:25:32 +0100
Received: by iamm17.iamm (SMI-8.6/SMI-SVR4)
id SAA08043; Wed, 3 Nov 1999 18:25:05 +0100
Message-Id: <199911031725.SAA08043 [at] iamm17 [dot] iamm>
Subject: Re: matrix inverse
To: nedialk [at] mcmail [dot] cis.mcmaster.ca (Ned Nedialkov)
Date: Wed, 3 Nov 1999 18:25:05 +0100 (MET)
Cc: rbk [at] usl [dot] edu, reliable_computing [at] interval [dot] usl.edu
In-Reply-To: from "Ned Nedialkov" at Nov 3, 99 12:17:56 pm
From: ae34 [at] rz [dot] uni-karlsruhe.de (Rudolf Lohner)
X-Mailer: ELM [version 2.4 PL21]
Content-Type: text
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Ned,
> I would like the entries of A to be floating-point numbers and perform all
> the computations in interval arithmetic, where the bounds are
> floating-point numbers.
in this case an algorithm like it is implemented for example by the
Pascal-XSC linear system solver LSS usually gives very tight bounds
(e.g. for Hilbert matrices up to dimension 20 the bounds are of maximal
accuarcy - if you premultiply the matrices by the gcd of their elements
to make them exactly representable in IEEE double).
The underlying algorithm goes back to Siegfried Rump's dissertation
and uses a multiple precision approximate inverse in a kind of
staggered representation. Nevertheless, all you need is pure IEEE
double plus a long accumulator.
You can find the Pascal-XSC code of this LSS solver on the our ftp
server in Karlsruhe
ftp.iam.uni-karlsruhe.de
amoung the sources of the Pascal-XSC compiler.
See in directory 'pub/pascal-xsc/sources' , get the file psrc.tar.Z
and look in directory 'ari' of the tar-archive for the files 'lss*.p'
Rudolf
o o
+-----/--------------------------------------------------------------/-----+
| Rudolf Lohner phone +49(721)608-6958 fax +49(721)695283 |
| Inst. f. Angewandte Mathematik Rudolf.Lohner [at] math [dot] uni-karlsruhe.de |
| Universitaet Karlsruhe (TH) http://www.uni-karlsruhe.de/~Rudolf.Lohner|
+--------------------------------------------------------------------------+
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 3 11:42:31 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA04421
for reliable_computing-outgoing; Wed, 3 Nov 1999 11:42:30 -0600 (CST)
Received: from bmw.CS.Berkeley.EDU (bmw.CS.Berkeley.EDU [128.32.46.234])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA04416
for ; Wed, 3 Nov 1999 11:42:27 -0600 (CST)
Received: from bmw.CS.Berkeley.EDU (demmel@localhost)
by bmw.CS.Berkeley.EDU (8.9.1a/8.9.1) with ESMTP id JAA28935;
Wed, 3 Nov 1999 09:42:23 -0800 (PST)
From: "James W. Demmel"
Message-Id: <199911031742.JAA28935 [at] bmw [dot] CS.Berkeley.EDU>
To: nedialk [at] mcmaster [dot] ca
cc: reliable_computing [at] interval [dot] usl.edu
Subject: Re: matrix inverse
In-reply-to: Your message of "Wed, 03 Nov 1999 12:06:40 EST."
<199911031706.MAA01148 [at] kula [dot] mcmaster.ca>
Date: Wed, 03 Nov 1999 09:42:22 -0800
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
The question of whether an interval matrix contains a singular matrix
is NP-hard. I believe the following is the reference:
S. Poljak and J. Rohn, "Checking robust nonsingularity is NP-hard",
Math. Control. Signals Syst. 6 (1993) pp 1-9
There are a lot of related optimization problems that have been shown to be
NP-hard.
Jim Demmel
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 4 15:45:17 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id PAA06658
for reliable_computing-outgoing; Thu, 4 Nov 1999 15:45:17 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id PAA06653
for ; Thu, 4 Nov 1999 15:44:51 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id OAA20686
for ; Thu, 4 Nov 1999 14:44:32 -0700 (MST)
Message-Id: <199911042144.OAA20686 [at] cs [dot] utep.edu>
Date: Thu, 4 Nov 1999 14:44:31 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: congratulations to Slava Nesterov
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: t+XLPj50sF9CFLqwX6G+/A==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
I have just learned that Slava Nesterov, the founding editor and the
Editor-in-Chief of our Reliable Computing journal, has successfully defended
his Habilitation Dissertation. Congratulations to Slava!
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 4 16:04:59 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id QAA06968
for reliable_computing-outgoing; Thu, 4 Nov 1999 16:04:59 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id QAA06961
for ; Thu, 4 Nov 1999 16:04:47 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id PAA20797
for ; Thu, 4 Nov 1999 15:04:34 -0700 (MST)
Message-Id: <199911042204.PAA20797 [at] cs [dot] utep.edu>
Date: Thu, 4 Nov 1999 15:04:33 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: interval session: preliminary info
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: mGTIhbuHyBf6VogEs9hR2g==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Preliminary information:
Please mark your calendars (details will follow)
**************************************************************************
Slava Nesterov is organizing a Special Session on Interval Computations at
**************************************************************************
IMACS-ACA'2000
International Association for Mathematics
and Computers in Simulation
6th International Conference on
Applications of Computer Algebra
June 25--28, 2000
Saint Petersburg, Russia
General Chair: Nikolay Vassiliev vasiliev [at] pdmi [dot] ras.ru
Program Chairs: Victor Edneral edneral [at] theory [dot] npi.msu.su
Richard Liska liska [at] siduri [dot] fjfi.cvut.cz
Michael Wester wester [at] math [dot] unm.edu
Scope:
The meeting will focus on actual or possible applications of nontrivial
computer algebra techniques to other fields and substantial interactions of
computer algebra with other fields.
Meeting Format:
The meeting will be run in the standard IMACS format where individuals are
invited to organize a special session. Individuals can propose a special
session by contacting the program chairs. All paper submissions must be
directed to an organizer of an appropriate special session.
Sponsored by:
*Steklov Institute of Mathematics at Saint Petersburg
*Euler International Mathematical Institute
*Saint Petersburg Mathematical Society
*Saint Petersburg State University
For more information, please see
http://www.pdmi.ras.ru/EIMI/2000/imacs/ or
http://math.unm.edu/aca.html (main ACA page)
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 4 16:54:16 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id QAA07390
for reliable_computing-outgoing; Thu, 4 Nov 1999 16:54:16 -0600 (CST)
Received: from mailgate.rz.uni-karlsruhe.de (exim [at] mailgate [dot] rz.uni-karlsruhe.de [129.13.64.97])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id QAA07385
for ; Thu, 4 Nov 1999 16:54:12 -0600 (CST)
Received: from iamk4503.mathematik.uni-karlsruhe.de (root [at] iamk4503 [dot] mathematik.uni-karlsruhe.de [129.13.129.3])
by mailgate.rz.uni-karlsruhe.de with smtp (Exim 3.02 #2)
id 11jVli-0001S0-00; Thu, 04 Nov 1999 23:54:10 +0100
Received: from math.uni-karlsruhe.de by iamk4503.mathematik.uni-karlsruhe.de (SMI-8.6/SMI-SVR4)
id XAA29978; Thu, 4 Nov 1999 23:54:09 +0100
Message-ID: <3822107E.EB21C538 [at] math [dot] uni-karlsruhe.de>
Date: Fri, 05 Nov 1999 00:02:22 +0100
From: Axel Facius
X-Mailer: Mozilla 4.61 [en] (X11; I; Linux 2.2.10 i686)
X-Accept-Language: en
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] usl.edu, validated_numerics@tu-harburg.de
Subject: Using Intlab on distributed environments (UNIX)
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Hi,
recently I installed Sigfried Rumps excellent Intlab but ran into
trouble due to our various platforms sharing one installation.
After installing, Intlab computes some error estimates which
are used to give rigerous bounds for standard functions with
intervall arguments. These error estimates are very hardware
dependent but are only stored in a file named 'stdfctsdata.mat'.
That is, if you share one Intlab installation with different
computers you may get wrong enclosures for standard functions.
To avoid this I modified the file 'startup.m' so that each
computer (determined via the shell command hostname) usese its
own installation directory.
Additionally I added the Matlab version to the name of the
configuration.
If startup.m cannot find a directory called
$MATLAB_HOME/toolbox/intlab._ it looks for
$HOME/matlab/intlab._. If even that fails
startup.m creates the latter and copies the platform independent
part of Intlab into it. To be exact: it copies everything found in
$MATLAB_HOME/toolbox/intlab. Thus you have to make shure that there
is no old 'stdfctsdata.mat' hanging around in this directory.
Afterwards intlab computes the values mentioned above.
If you want to install this 'local' Intlab configuration globaly,
you (or your admin) just have to copy the entire directory
$HOME/matlab/intlab._ to
$MATLAB_HOME/toolbox/intlab._.
For those who have trouble with attachments I included my
'startup.m' here. Make shure that everybody who wants to use Intlab
has this file in his/her $HOME/matlab/.
Hope that helps,
Axel
__o __o
`\<, `\<,
___________________()/ ()_____________()/ ()____________________________
Axel Facius Tel.: (+49) 721 - 937 54 85
Inst. f. Angewandte Mathematik Fax: (+49) 721 - 38 59 79
Universitaet Karlsruhe (TH) mailto:axel.facius [at] math [dot] uni-karlsruhe.de
D-76128 Karlsruhe, Germany http://www.uni-karlsruhe.de/~axel.facius
________________________________________________________________________
-----8<----------8<----------8<--------8<--------8<---------8<--------8<------
% STARTUP Initialization of paths, global variables etc.
% Adapt this to your local needs
%
%
% written 10/16/98 S.M. Rump
% modified 11/05/98 allow blanks in path name, Max Jerrell, Flagstaff
% modified 11/04/99 workaround for distributed environments A. Facius
% (axel.facius [at] math [dot] uni-karlsruhe.de)
%
clear all
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Default setting: change these line to your needs %%%%%%%%%%%%%%%
%VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
TOOLBOX_PATH = '/opt/matlab5/toolbox/';
%AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[err, hostname] = unix('hostname');
if err
error('**** Cannot determine the hostname.');
end
hostname(length(hostname))='';
vers = version;
vers = strrep( vers, ' ', '_' );
vers = strrep( vers, '(', '' );
vers = strrep( vers, ')', '' );
id = [ hostname '_' vers ];
PATH = [ TOOLBOX_PATH 'intlab.' id '/' ];
[err, res] = unix( [ 'test -d ' PATH ] );
if err
disp( '**** Intlab is not globaly configured for this machine.');
disp( '**** Ask your system administrator to do so.');
disp( '**** Try to use a local configuration...');
[err, homedir] = unix('echo $HOME');
if err
error('**** Cannot determine the home-directory.');
end
homedir(length(homedir))='';
PATH = [ homedir '/matlab/' ];
[err, res] = unix( [ 'test -d ' PATH ] );
if err
[err, res] = unix( [ 'mkdir ' PATH ] );
if err
error('**** ERROR: Cannot create a local matlab-directory.');
end
end
PATH = [ PATH 'intlab.' id '/' ];
[err, res] = unix( [ 'test -d ' PATH ] );
if err
[err, res] = unix( [ 'mkdir ' PATH ] );
if err
error('**** ERROR: Cannot create a local config-directory.');
end
[err, res] = unix( [ 'cp -R ' TOOLBOX_PATH 'intlab/* ' PATH ] );
end
disp( '**** ... ok.' );
disp( [ '**** Using local intlab configuration in ' PATH '.' ] );
else
disp( [ '**** Using global intlab configuration in ' PATH '.' ] );
end
pwd = cd;
cd( PATH );
addpath( PATH , ...
[ PATH 'intval' ] , ...
[ PATH 'gradient' ] , ...
[ PATH 'slope' ] , ...
[ PATH 'utility' ] , ...
[ PATH 'long' ])
%%%%%%%%%% initialize sparse systems
spparms('autommd',0); % switch off automatic band reduction
%%%%%%%%%% initialize interval toolbox (see "help intvalinit")
intvalinit('Init') % Initialize global constants
intvalinit('CheckRounding') % Check directed rounding
%%%%%%%%%% initialize gradient toolbox
gradientinit
%%%%%%%%%% initialize slope toolbox
slopeinit
%%%%%%%%%% initialize long toolbox
longinit('Init')
%%%%%%%%%% set environment
format compact
cd(PATH) % blanks allowed in path name
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Default setting: change these lines to your needs %%%%%%%%%%%%%%
%VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
intvalinit('Display_')
intvalinit('RigorousStdFcts')
intvalinit('FastIVMult')
%AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
intlablogo(1)
pause(1)
close
clear
cd( pwd );
-----8<----------8<----------8<--------8<--------8<---------8<--------8<------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 6 05:55:48 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id FAA10633
for reliable_computing-outgoing; Sat, 6 Nov 1999 05:55:47 -0600 (CST)
Received: from visla.utia.cas.cz (root [at] visla [dot] utia.cas.cz [147.231.12.1])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id FAA10628
for ; Sat, 6 Nov 1999 05:55:43 -0600 (CST)
Received: from [147.231.11.66] (klicava.site.cas.cz [147.231.11.66])
by visla.utia.cas.cz (8.9.3/8.9.3) with SMTP id MAA16105;
Sat, 6 Nov 1999 12:55:35 +0100 (MET)
X-NUPop-Charset: IBM 8-Bit
Date: Sat, 6 Nov 99 13:39:49 CET
From: "Jiri Rohn"
Reply-To: rohn [at] uivt [dot] cas.cz
Message-Id: <49191.rohn [at] uivt [dot] cas.cz>
To: reliable_computing [at] interval [dot] usl.edu, nedialk [at] mcmaster [dot] ca
Subject: inverse interval matrix
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Ragarding the request by Ned Nedialkov:
Inverse interval matrix is handled in my equally-named paper in SIAM J.
Numer. Anal. 30(1993), 864-870. A method I would recommend for computing
enclosures is contained in Theorem 3 of my paper "Cheap and tight bounds:
The recent result by E. Hansen can be made more efficient", Interval
Computations 4(1993), 13-21.
As pointed out by Vladik, NP-hardness of computing the exact iterval inverse
is due to Greg Coxson. In fact he proved the result in 1993, but published
it only this year.
Jiri Rohn
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 7 12:26:56 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id MAA12152
for reliable_computing-outgoing; Sun, 7 Nov 1999 12:26:56 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id MAA12147
for ; Sun, 7 Nov 1999 12:26:49 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id LAA03464
for ; Sun, 7 Nov 1999 11:26:46 -0700 (MST)
Message-Id: <199911071826.LAA03464 [at] cs [dot] utep.edu>
Date: Sun, 7 Nov 1999 11:26:46 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: from NA Digest: a conference co-organized by Kaj Madsen
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: FJmo+Zz8YYjStQSKHqONLg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
From: Ake Bjorck
Date: Fri, 5 Nov 1999 16:06:15 +0100 (MET)
Subject: Conference for the 40th Anniversary of BIT
International Conference on NUMERICAL MATHEMATICS
on the 40th Anniversary of the journal BIT
August 9--12, 2000
Lund, Sweden
First Announcement and Call for Papers
SCOPE
Topics central to BIT will be emphasized. Several invited talks will survey
important recent developments in areas including numerical solution
of odes, numerical linear algebra
CONFERENCE LOCATION
The conference is hosted by the Department of Mathematics of the University
of Lund located in southern Sweden.
ORGANIZATION COMMITTEE
{\AA}ke Bj{\"o}rck (Link{\"o}ping University)
Gustaf S{\"o}derlind (Lund University)
Kaj Madsen (Technical University of Denmark)
PROGRAM COMMITTEE
Per Christian Hansen, Lyngby
Olavi Nevanlinna, Helsinki
Syvert N{\o}rsett, Trondheim
Axel Ruhe, Gothenburg
Schedule and themes:
INVITED SPEAKERS
The following speakers have been invited:
G. H. Golub (Stanford University)
G. W. Stewart (University of Maryland)
E. Hairer (Universit\'e de Gen\`eve)
H. Van der Vorst (Utrecht University )
MINISYMPOSIA over the following topics central to BIT will be organized:
Geometric integration (Syvert N\o rsett)
Generalized eigenproblems (Axel Ruhe)
Inverse and illposed problems (Per Christian Hansen)
Iterative methods (Olavi Nevanlinna)
Ordinary differential equations (Gustaf S\"oderlind)
A meeting with the editorial board of BIT is scheduled.
CONTRIBUTED TALKS
Participants wishing to present a contributed talk should submit by e-mail
an extended abstract (1-2 pages) written in LaTeX to Prof. Gustaf
S{\"o}derlind,
Gustaf.Soderlind [at] na [dot] lu.se.
Deadline for submission is March 1, 2000. Notification of acceptance will
be given by April 15, 1999. Participants should register by June 15, 2000
for their talk to be included in the Conference program.
PROCEEDINGS
Papers from the conference will be published in BIT Numerical Mathematics,
Issue 41:1. Deadline for paper submission is September 15, 2000.
REGISTRATION
The Conference fee is 175$ US for early registration until May 31, 2000
and 200$ US after this date or on site registration. The fee includes:
a welcoming reception, coffee breaks, an afternoon excursion over the new
bridge from Malm{\"o} to Copenhagen, where the conference dinner will take
place.
DEADLINES
Early registration: June 15, 2000
Abstract submission: March 1, 2000
Notification of acceptance: April 15, 2000
Additional information about the Conference may be obtained by writing to
BIT Conference 2000, Center for Mathematical Sciences, Lund University,
Box 118, SE-221 00 Lund, Sweden or by visiting the web site of the Conference
at the address: http://www.maths.lth.se/na/
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 8 11:20:29 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA14044
for reliable_computing-outgoing; Mon, 8 Nov 1999 11:20:29 -0600 (CST)
Received: from thrush.prod.itd.earthlink.net (thrush.prod.itd.earthlink.net [207.217.121.96])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA14039
for ; Mon, 8 Nov 1999 11:20:26 -0600 (CST)
Received: from company.mail (ip241.garden-city2.ny.pub-ip.psi.net [38.26.50.241])
by thrush.prod.itd.earthlink.net (8.8.7/8.8.5) with SMTP id JAA13774
for ; Mon, 8 Nov 1999 09:20:22 -0800 (PST)
Received: from ramas.com [192.0.0.5] by company.mail [127.0.0.1] with SMTP (MDaemon.v2.7.SP5.R) for ; Mon, 08 Nov 1999 12:04:51 -0500
Message-ID: <38270261.E754D63C [at] ramas [dot] com>
Date: Mon, 08 Nov 1999 12:03:29 -0500
From: Scott Ferson
Organization: Applied Biomathematics
X-Mailer: Mozilla 4.6 [en] (Win95; I)
X-Accept-Language: en
MIME-Version: 1.0
To: "reliable_computing [at] interval [dot] usl.edu"
Subject: workshop announcement
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-MDaemon-Deliver-To: reliable_computing [at] interval [dot] usl.edu
X-Return-Path: scott [at] ramas [dot] com
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
The Society for Risk Analysis is sponsoring a workshop on
interval analysis, Monte Carlo methods, fuzzy arithmetic and
probability bounds analysis. A synopsis appears below and
details are available at http://www.ramas.com/interval.htm
Scott Ferson
Applied Biomathematics, 516-751-4350, fax -3435
WORKSHOP
BEYOND POINT ESTIMATES
Risk Assessment Using Interval, Monte Carlo, Fuzzy and Bounding Methods
Sunday, 5 December 1999
Society for Risk Analysis Annual Meeting
Atlanta Marriott Marquis
Atlanta, Georgia
Abstract
This workshop introduces interval analysis, Monte Carlo methods,
fuzzy arithmetic and probability bounds analysis for propagating
uncertainty in quantitative risk analyses where data are very
limited. Interval analysis, although less powerful than other
methods when information is abundant, can be used for analyzing
uncertainty of all kinds no matter what its nature or source.
As the simplest method for handling uncertain quantities, we use
it to demonstrate many of the commonalities that unite all the
approaches. Some of the details of uncertainty arithmetic can
be very subtle and inattention to them may lead to seriously
erroneous conclusions. The methods will be applied to several
examples and case studies. Along with a workbook of illustrations
used during the workshop, attendees will be provided a CD of
software including executable programs and public-domain source
code.
Topics will include
Interval analysis
Monte Carlo methods
Fuzzy arithmetic
Probability bounds analysis
The algebra you already know can hurt you
Backcalculation untangles equations involving uncertainty
How to specify inputs when you don't know much
How to model correlation and dependencies
How to account for model uncertainty
Comparisons among different methods for propagating uncertainty
Combining bounding methods with probability theory
Decisions under incomplete information
Examples and case studies include
Ground water contamination
Event-tree safety assessment
Setting cleanup targets
Endangered species conservation strategies
Wildlife exposure to environmental hexachlorobenzene
You can register for the workshop by contacting the Society for
Risk Analysis at 703-790-1745, fax -2672, or SRA [at] BurkInc [dot] com.
Pre-registration before 15 November is $300; on-site registration
is $360.
From owner-reliable_computing [at] interval [dot] usl.edu Tue Nov 9 13:34:16 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA16046
for reliable_computing-outgoing; Tue, 9 Nov 1999 13:34:16 -0600 (CST)
Received: from lukla.Sun.COM (lukla.Sun.COM [192.18.98.31])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA16041
for ; Tue, 9 Nov 1999 13:34:12 -0600 (CST)
Received: from engmail1.Eng.Sun.COM ([129.146.1.13])
by lukla.Sun.COM (8.9.3+Sun/8.9.3) with ESMTP id MAA06918;
Tue, 9 Nov 1999 12:34:09 -0700 (MST)
Received: from ha-sims.eng.sun.com (phys-thestorka.Eng.Sun.COM [129.146.1.231])
by engmail1.Eng.Sun.COM (8.9.1b+Sun/8.9.1/ENSMAIL,v1.6) with ESMTP id LAA06646;
Tue, 9 Nov 1999 11:34:08 -0800 (PST)
Received: from gww (gww.Eng.Sun.COM [129.146.78.116])
by ha-sims.eng.sun.com (Sun Internet Mail Server sims.4.0.1999.06.13.00.20)
with SMTP id <0FKY005FI3JH28@ha-sims.eng.sun.com>; Tue,
9 Nov 1999 11:30:53 -0800 (PST)
Date: Tue, 09 Nov 1999 11:30:53 -0800 (PST)
From: William Walster
Subject: Sun f95 Early Access with Interval Support
To: reliable_computing [at] interval [dot] usl.edu, validated_numerics@tu-harburg.de,
interval [at] cs [dot] utep.edu
Reply-to: William Walster
Message-id: <0FKY005FJ3JH28@ha-sims.eng.sun.com>
MIME-version: 1.0
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4m sparc
Content-type: TEXT/plain; charset=us-ascii
Content-MD5: u8tMKxhUhtS+oICOt/QD1A==
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear members of the Interval Community:
The early access (beta test) version of Sun's Fortran 95 compiler with
support for intrinsic interval data types is now available. See:
http://access1.sun.com/workshop6ea/
This is a major accomplishment, to which many in the interval community
have contributed. Thanks!
Commercial interval support provides a number of opportunities for members
of the interval community and for Sun. Members of the interval community
have an important role to play in helping to make sure support for intervals
is a commercial success. If it is, both the interval community and
Sun will benefit.
Because intervals are still new to most of the computing world, and because
some new interval support functionality is being introduced in the f95
compiler, customer support may be an issue. Sun can't undertake a wholesale
education effort on the methods and benefits of interval arithmetic right now;
getting the existing capabilities known and used is the immediate goal. To
help with the education effort, support from the interval community will be
beneficial to all concerned. Most importantly, it will help those new to
intervals to get questions answered and to be able to access as many existing
interval programs as possible:
a) so they don't have to reinvent these codes; and
b) so they can see how well constructed interval algorithms are
developed, implemented and tested using the f95 compiler.
The following plan is designed to maximize our collective upside opportunity.
Early access is scheduled run for 16 weeks. In the first phase, it will be
helpful to keep access to Fortran developers in the interval community.
Feedback, both about bugs and the content of draft documentation will be
most helpful.
Feedback will be facilitated by an email alias within which EA participants
can discuss problems/issues/concerns, and where possible solutions
can be reviewed. I hope there will be few if any controversies. If any
develop, it will be helpful to confine them to this alias, until they can
be constructively resolved.
Once through the first phase and any serious problems are resolved, we
can invite more members of the interval community, companies, and
researchers to participate more fully. At this point, it will be critical
for members of the interval community help support those users who are new
to intervals. Sun's resources will be best spent analyzing and fixing
whatever problems are uncovered. If interval community support can
continue after the compiler ships, it will benefit all concerned. A
positive response to intervals and the compiler can be leverage for
additional funding of interval cooperative research and development,
from which more end-user applications can be developed.
In parallel with the above, it will also be helpful if as much
existing interval code as possible is ported onto the f95 compiler. This
should be a relatively easy. Posting these codes and libraries to the
Internet will provide new users with existing routines to use and from
which they can clone and build their own routines. If these codes, test
cases, and documentation can be posted to the Internet, Sun will be able
to incorporate them into its application test suites. If documentation
is available in published books or manuscripts, pointers to them will be
helpful. This will be a good opportunity for the excellent work done at
many universities and Professor Kulisch's institute to get wide exposure.
Please let me know if there are any other suggestions you have that
will help make this interval product rollout successful, both for
the interval community and for Sun.
Thanks in advance for your help and support,
Bill
G. William (Bill) Walster, Ph.D.
Interval Technology Engineering Manager
Sun Microsystems, Inc.
901 San Antonio Road, MS UMPK16-304
Palo Alto, CA 94303-4900
(650) 786-9004 Direct
(650) 786-9551 Fax
bill.walster [at] eng [dot] sun.com
P.S. Look for us at SC99 in Portland.
From owner-reliable_computing [at] interval [dot] usl.edu Tue Nov 9 20:38:31 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id UAA16714
for reliable_computing-outgoing; Tue, 9 Nov 1999 20:38:31 -0600 (CST)
Received: from apollon.ito.ecei.tohoku.ac.jp (apollon.ito.ecei.tohoku.ac.jp [130.34.197.37])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id UAA16709
for ; Tue, 9 Nov 1999 20:38:26 -0600 (CST)
Received: from localhost (micrus [130.34.197.15])
by apollon.ito.ecei.tohoku.ac.jp (8.8.8/3.6W-) with ESMTP id LAA06326;
Wed, 10 Nov 1999 11:36:19 +0900 (JST)
To: reliable_computing [at] interval [dot] usl.edu
cc: miyakawa [at] ito [dot] ecei.tohoku.ac.jp
Subject: TCS2000
X-Mailer: Mew version 1.92.4 on XEmacs 20.4 (Emerald)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <19991110114011R.miyakawa [at] ito [dot] ecei.tohoku.ac.jp>
Date: Wed, 10 Nov 1999 11:40:11 +0900
From: Shinya MIYAKAWA
X-Dispatcher: imput version 971024
Lines: 150
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Apologies if you receive multiple copies.
--------
call for papers
IFIP International Conference on Theoretical Computer Science
IFIP TCS2000
--- Exploring New Frontiers of Theoretical Informatics ---
August 17 - 19, 2000
Tohoku University, Sendai, Japan
IFIP TCS2000 is the first International Conference on Theoretical Computer
Science organized by the IFIP TC1 on Foundations of Computer Science. Major
topics of the conference are follows:
Track (1): Algorithms, Complexity and Models of Computation
analysis and design of algorithms --- algorithm experimentation ---
continuous algorithms and complexity --- computational complexity ---
descriptional complexity --- cellular automata and machines, automata
and formal languages --- hardware algorithms and parallel algorithms
--- computational learning theory --- algorithmic aspects in discovery
science --- cryptography --- combinatorics --- probabilistic and
randomized algorithms --- molecular computing and algorithmic aspects
of bioinformatics --- quantum computing --- neural network computing
--- evolutionary and genetic algorithms --- computational geometry ---
computational and mathematical finance --- bridging complexity and
semantics.
Track (2): Logic, Semantics, Specification and Verification
logic and semantics for programs and languages --- foundations of
system specification --- term rewriting systems --- proofs and
specifications in computer science --- types and category theory in
computer science --- theoretical aspects of specification and
verification of hardware and software --- theoretical aspects of
software concepts --- concurrency theory --- theory of parallel and
distributed systems --- theory of internet languages and systems ---
constructive and non-standard logics in computer science ---
foundations of security --- theoretical foundations of data bases ---
logic, specification and verification of hybrid and real-time
systems --- theoretical foundations of open systems --- bridging
semantics and complexity.
Submissions on the above topics and related topics are invited. Submitted
papers should preferably be typeset in LaTeX2e using the Springer document
class llncs for the LNCS format, see
http://www.springer.de/comp/lncs/authors.html
(the command \pagestyle{plain} turns on page numbering), and no longer than
14 pages. They should be sent in Postscript by email to one of the
following addresses by January 28 (Friday), 2000:
for Track (1), tcs2000-track1 [at] is [dot] s.u-tokyo.ac.jp;
for Track (2), tcs2000-track2 [at] is [dot] s.u-tokyo.ac.jp.
A submission should include the track name for the submission, the title of
the paper, names and affiliations of authors, an abstract up to 300 words,
and the contact author's name, address, phone number, fax number, and email
address. The submission must be in English, and it should provide a summary
of the main results and their details to allow the program committee to
assess their merits and significance, including references and comparisons.
The result of the paper must be unpublished and not submitted for
publication elsewhere, including journals and the proceedings of other
symposia or workshops. One author of each accepted paper should be able to
present it at the conference.
Important Dates:
January 28, 2000: Deadline for submission of papers
April 7, 2000: Notification of acceptance
May 5, 2000: Final camera-ready text due
See http://hagi.is.s.u-tokyo.ac.jp/tcs2000/ for further information about the
submission procedure.
The program will consist of:
Plenary Invited Talks
Mart\'in Abadi (Bell Labs, Lucent Technologies)
Masami Hagiya (U. Tokyo)
Madhu Sudan (MIT)
Track (1) Invited Talks
Ernst Mayr (TU Muenchen)
Shu Tezuka (IBM Tokyo Research Lab)
Mihalis Yannakakis (AT\&T Research)
Track (2) Invited Talks
Thomas Henzinger (UC Berkeley & MPI-Saarbrucken)
Naoki Kobayashi (U. Tokyo)
Gordon Plotkin (U. Edinburgh)
Banquet Speech
Michael O. Rabin (Harvard U.)
as well as the selected contributed talks and a panel discussion.
The Proceedings, published as a volume of Lecture Notes in Computer
Science, Springer-Verlag, will be available at the conference. See
http://tcs2000.ito.ecei.tohoku.ac.jp/tcs2000/ for general information
about the IFIP TCS2000 Conference.
Program Committee Co-Chairs
Track (1): Algorithms, Complexity and Models of Computation
Jan van Leeuwen (U. Utrecht)
Osamu Watanabe (Tokyo Inst. of Technology)
Track (2): Logic, Semantics, Specification, and Verification
Masami Hagiya (U. Tokyo)
Peter D. Mosses (U. Aarhus)
Program Committee
Track (1): Ricardo Baeza-Yates (U. Chile), Siu-Wing Cheng (Hong Kong UST),
Felipe Cucker (City U. Hong Kong),
Rosario Gennaro (IBM T.J. Watson Research),
Alan Gibbons (U. Liverpool), Andrew V. Goldberg (InterTrust STAR Lab, USA),
Ernst Mayr (TU Muenchen), Hiroshi Nagamochi (Kyoto U.),
Kouichi Sakurai (Kyushu U.), Paul Vitanyi (CWI, Amsterdam),
Jiri Wiedermann (Academy of Sciences, Prague), Takashi Yokomori (Waseda U.)
Track (2): Samson Abramsky (U. Edinburgh), Egidio Astesiano (U. Genova),
Luca Cardelli (Microsoft, Cambridge), Robert Constable (Cornell U.),
Javier Esparza (TU Muenchen), Naoki Kobayashi (U. Tokyo),
Jos\'e Meseguer (SRI, Menlo Park), Benjamin Pierce (U. Pennsylvania),
Davide Sangiorgi (INRIA, Sophia Antipolis), John Staples (U. Queensland),
Andrzej Tarlecki (Warsaw U.),
P. S. Thiagarajan (Chennai Math. Inst., India),
Kazunori Ueda (Waseda U.), Naoki Yonezaki (Tokyo Inst. Tech.)
Conference Co-Chairs
Giorgio Ausiello (IFIP TC1 Chair and U. Roma "La Sapienza")
Takayasu Ito (Tohoku U.)
Steering Committee
Giorgio Ausiello (U. Roma) , Wilfried Brauer (TU Muenchen),
Takayasu Ito (Tohoku U.), Michael O. Rabin (Harvard U.),
John Staples (U. Queensland), Joseph Traub (Columbia U.)
Organizing Committee Co-Chairs
Setsuo Arikawa (Kyushu U.), Yasuyoshi Inagaki (Nagoya U.),
Takayasu Ito (Tohoku U.)
The IFIP TCS2000 conference is organized by the IFIP TC1 on Foundations of
Computer Science in cooperation with Information Processing Society of Japan,
Japan Society of Software Science and Technology, Institute of Electronics,
Information and Communication Engineers in Japan*, European Association of
Theoretical Computer Science, Association of Symbolic Logic, and Association
for Computing Machinery-SIGACT. (* indicates "to be verified".)
E-mail address for any inquiry: TCS2000 [at] ito [dot] ecei.tohoku.ac.jp
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 11 07:27:59 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id HAA19858
for reliable_computing-outgoing; Thu, 11 Nov 1999 07:27:59 -0600 (CST)
Received: from interval.usl.edu (rbk5287@interval [130.70.43.77])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id HAA19853
for ; Thu, 11 Nov 1999 07:27:53 -0600 (CST)
Message-Id: <199911111327.HAA19853 [at] interval [dot] usl.edu>
Date: Thu, 11 Nov 1999 07:27:53 -0600 (CST)
From: "Kearfott R. Baker"
Reply-To: "Kearfott R. Baker"
Subject: Automated deduction workshop
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: kji3+iPw+RitqZxVM51+Yg==
X-Mailer: dtmail 1.2.1 CDE Version 1.2.1 SunOS 5.6 sun4m sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
------------- Begin Forwarded Message -------------
Organization: Universitaet des Saarlandes, D 66123 Saarbruecken
To: TOO MANY NAMES FOR LIST SERVER TO PROCESS PROPERLY
Reply-to: Michael Kohlhase
Subject: CADE-17 Second Call for Workshops and Tutorials
Date: Thu, 11 Nov 1999 08:44:08 +0100
From: Michael Kohlhase
[Apologies to all that receive this call more than once]
CADE-17
The 17th International Conference on Automated Deduction
June 17-20, 2000
Pittsburgh, Pennsylvania, USA
http://www.research.att.com/conf/cade/
Second CALL FOR WORKSHOPS AND TUTORIALS
June 16. and 21. 2000
CADE is the major forum for the presentation of new research in all aspects
of automated deduction. Proposals for workshops and for tutorials are
solicited. Tutorials will run June 16. and workshops also on June 21.
Workshops will ordinarily run a whole day, and tutorials for half a day.
Workshop Topics
---------------
Recent CADE workshops have included term schematizations and their
applications, reasoning, automation of proofs by induction, empirical studies
in logic algorithms, mechanization of partial functions, proof search in
type-theoretic languages, automated model building, evaluation of automated
theorem-proving systems, strategies in automated deduction, automated theorem
proving in software engineering and in mathematics, integration of symbolic
computation and deduction.
Workshops may have the same topic as those of previous workshops, and this
practice is encouraged.
Tutorial Topics
---------------
Recent CADE tutorials have included equality reasoning in semantic tableaux,
proof systems for nonmonotonic logics, rewrite techniques in theorem proving,
proof planning, parallelization of deduction strategies, resolution decision
methods, constructive type theory, the use of semantics in Herbrand-based
proof procedures, logical frameworks, theorem proving by the inverse method,
deduction methods based on boolean rings, higher-order equational logic, and
term indexing in automated reasoning.
Tutorials may be introductory, intermediate, or advanced.
Proposals
---------
Anyone wishing to organize a workshop or tutorial in conjunction with CADE-17
should send (e-mail preferred) a proposal no longer than two pages to the
workshop chair by November 30, 1999. The proposal should describe the topic
of the proposed workshop or tutorial and explain why the topic is relevant to
CADE. Proposals will be evaluated, and decisions will be communicated by
December 15. 1999. Further information about the arrangements for workshops
and tutorials can be obtained from the CADE-17 Web site.
Proposal deadline: November 30, 1999
Notification of acceptance: December 15, 1999
Workshop paper deadline: April 1, 2000
Workshop paper notification: May 1, 2000
PROGRAM CHAIR: Conference Chair: WORKSHOP CHAIR:
David McAllester Frank Pfenning Michael Kohlhase
AT&T Labs-Research Carnegie Mellon University Universit"at des
Saarlandes
dmac [at] research [dot] att.com fp+@cs.cmu.edu kohlhase [at] cs [dot] uni-sb.de
------------- End Forwarded Message -------------
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 11 09:03:23 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id JAA20245
for reliable_computing-outgoing; Thu, 11 Nov 1999 09:03:23 -0600 (CST)
Received: from skiff.cs.vu.nl (root [at] skiff [dot] cs.vu.nl [192.31.231.56])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id JAA20240
for ; Thu, 11 Nov 1999 09:03:20 -0600 (CST)
Received: by skiff.cs.vu.nl (Smail #62)
id m11lvkS-000TgXC; Thu, 11 Nov 99 16:02 +0100
Message-Id:
From: femke [at] cs [dot] vu.nl (Raamsdonk van F)
Subject: CL2000: call for workshop proposals
To: reliable_computing [at] interval [dot] usl.edu
Date: Thu, 11 Nov 1999 16:02:52 +0100 (MET)
X-Mailer: ELM [version 2.4 PL24alpha3]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
*** apologies for multiple copies ***
CL2000
First International Conference on Computational Logic
Imperial College, London, UK, 24th to 29th July, 2000
http://www.doc.ic.ac.uk/cl2000/
CALL FOR WORKSHOP PROPOSALS
CL2000 is the first conference in a major new series of annual
international conferences bringing together the various communities of
researchers who have a common interest in Computational Logic.
CL2000 includes seven streams covering various subfields of
computational logic. DOOD2000 (6th International Conference on Rules
and Objects in Databases) and LOPSTR2000 (10th International Workshop
on Logic-based Program Synthesis and Transformation) will be streams
within CL2000. Moreover, the International Conference on Logic
Programming (ICLP) is now integrated into CL2000. ILP2000 (10th
International Conference on Inductive Logic Programming) is also
collocated with CL2000.
The organisation of CL2000 will provide facilities for half-day and
one-day workshops, to be held on Saturday July 29th.
Researchers and practitioners are invited to submit proposals for
workshops on topics in computational logic.
Anyone wishing to organise a workshop should send (possibly by email,
in text or html format) a proposal no longer than two pages to the
workshop coordinator by
December 20, 1999
The proposal should describe the topic of the proposed workshop and
its relevance to computational logic. Besides the contact information
and the list of the organisers, the proposal should contain - when
applicable - the following information:
- proposed duration of the workshop (half day/one day),
- description of previously organised similar workshops,
- expected number of participants,
- character of the workshop (formal/informal, via
submission/invitation),
- plans for publication of the proceedings.
The workshop organisers will be responsible for maintaining a
homepage, and for producing one hard copy of the proceedings in A4 or
US-letter format. Organisers who whish to use a format different than
A4 or US-letter are expected to produce the needed copies of
proceedings as well.
Proposals will be evaluated by the program committee and decisions
will be made by January 10, 2000. Further information about the
arrangements for workshops can be obtained from the workshop coordinator.
Workshop Coordinator:
Sandro Etalle
Dept. of Computer Science,
University of Maastricht,
P.O. Box 616, 6200 MD Maastricht
email: etalle [at] cs [dot] unimaas.nl
Fax: ++31 (0)43 3884897
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 00:35:53 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id AAA21264
for reliable_computing-outgoing; Fri, 12 Nov 1999 00:35:52 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id AAA21259
for ; Fri, 12 Nov 1999 00:35:13 -0600 (CST)
Received: (qmail 6645 invoked from network); 12 Nov 1999 06:57:24 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 12 Nov 1999 06:57:24 -0000
Received: from localhost (sheela@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id MAA06980
for ; Fri, 12 Nov 1999 12:03:07 +0530 (IST)
Date: Fri, 12 Nov 1999 12:03:07 +0530 (IST)
From: "Sheela S.(98423301)"
Reply-To: "Sheela S.(98423301)"
To: reliable_computing [at] interval [dot] usl.edu
Subject: methods with convergence order higher than two
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Hello,
I am a Ph.D student working with the applications of IA. Would like to
know whether there are any methods to construct forms with convergence
order 3 or 4 for the evaluation of ranges of functions with several
variables.
Thanking you in advance,
sheela
--------------------------------------------------------------------------------
Sheela Unnikrishnan (022-5772203)
Research Scholar, Room No.6,
Systems & Control Dept QIP Bldg 1
IIT Bombay, IIT Bombay
400076. 400076
India India
*****************************************************************************|
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 11:11:34 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA22692
for reliable_computing-outgoing; Fri, 12 Nov 1999 11:11:34 -0600 (CST)
Received: from cosmos.imag.fr (cosmos.imag.fr [147.171.130.1])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA22687
for ; Fri, 12 Nov 1999 11:11:22 -0600 (CST)
Received: from adraste.imag.fr (adraste.imag.fr [147.171.130.20])
by cosmos.imag.fr (8.9.3/8.8.5) with ESMTP id SAA25008;
Fri, 12 Nov 1999 18:06:08 +0100 (MET)
From: Dongming Wang
Received: (from wang@localhost)
by adraste.imag.fr (8.8.5/8.8.5) id SAA15445;
Fri, 12 Nov 1999 18:05:30 +0100 (MET)
Date: Fri, 12 Nov 1999 18:05:30 +0100 (MET)
Message-Id: <199911121705.SAA15445 [at] adraste [dot] imag.fr>
To: adg2000 [at] inf [dot] ethz.ch
Subject: ADG 2000 - Call for Papers
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
* * * * * Apologies for multiple copies - Please distribute * * * * *
----------- http://www-calfor.lip6.fr/~wang/ADG2000/index.html ---------------
The Third International Workshop
on
Automated Deduction in Geometry
Zurich, Switzerland, September 25-27, 2000
The International Workshops on Automated Deduction in Geometry (ADG) have
become a forum to exchange ideas and views, to present research results and
progress, and to demonstrate software tools. Applications of ADG to CAGD/CAD,
computer vision and geometry education presented at the previous two workshops
held in Beijing, August 1998 and Toulouse, September 1996 shed new light on
the perspectives of ADG. The third workshop ADG 2000 to be held in Zurich,
Switzerland, September 25-27, 2000 will continue ADG's emphasis on theory
and algorithms, implementation, experiments, and applications to science,
engineering and industry.
Important Dates
Deadline for extended abstract submission: June 20, 2000
Notification of acceptance or rejection: July 20, 2000
Workshop taking place: September 25-27, 2000
Deadline for full paper submission: November 20, 2000
Topics
Specific topics for ADG 2000 include (but are not limited to):
- Polynomial algebra, invariant and coordinate-free methods, probabilistic,
synthetic, and logic approaches, techniques for automated geometric
reasoning from discrete mathematics, combinatorics, and numerics
- Symbolic and numeric methods for geometric computation, geometric
constraint solving, automated generation/reasoning and manipulation
with diagrams
- Design and implementation of geometry software, special-purpose tools,
automated theorem provers, experimental studies
- Applications of ADG to mechanics, geometric modeling, CAGD/CAD, computer
vision, robotics and education.
Program Committee
Shang-Ching Chou (Wichita, USA)
Luis Farinas del Cerro (Toulouse, France)
Andreas Dress (Bielefeld, Germany)
Desmond Fearnley-Sander (Hobart, Australia)
Xiao-Shan Gao (Beijing, China)
Hoon Hong (Raleigh, USA)
Deepak Kapur (Albuquerque, USA)
Juergen Richter-Gebert (Co-chair, Zurich, Switzerland)
Bernd Sturmfels (Berkeley, USA)
Dongming Wang (Co-chair, Grenoble/Paris, France)
Volker Weispfenning (Passau, Germany)
Neil White (Gainesville, USA)
Walter Whiteley (Toronto, Canada)
Franz Winkler (Linz, Austria)
Lu Yang (Chengdu, China)
Submission
Potential participants of ADG 2000 are invited to submit an extended abstract
of three or more pages or a full paper describing their work to be presented
at ADG 2000. The submitted extended abstracts and full papers will be reviewed
by members of the program committee (PC) for presentation at the workshop.
Electronic submissions are preferred, and should be sent to both of the PC
co-chairs:
Prof. Juergen Richter-Gebert
Theoretische Informatik
ETH Zentrum
Haldeneggsteig 4 / Weinbergstrasse
CH-8092 Zurich, Switzerland
E-mail richter [at] inf [dot] ethz.ch
Fax +41 1 632 1172
Dr. Dongming Wang
Laboratoire d'Informatique de Paris 6
Universite Pierre et Marie Curie - CNRS
4, place Jussieu
F-75252 Paris Cedex 05, France
E-mail wang [at] calfor [dot] lip6.fr
Fax +33 1 44 27 40 42
The program of ADG 2000 will contain two invited talks. The names of the
invited speakers will be announced shortly.
Publication
Authors of the extended abstracts and full papers accepted for presentation
at the workshop will be invited to submit their full and/or revised papers
for publication in the proceedings of ADG 2000 after the workshop. The
submitted papers will be formally reviewed by PC members and external
referees. It is expected that the accepted papers will be published as a
volume in the LNAI series by Springer-Verlag. The proceedings of ADG '96
and ADG '98 appeared as LNAI 1360 and LNAI 1669 respectively.
Workshop Site
The workshop ADG 2000 will take place at ETH Zurich (Federal Institute of
Technology) in Switzerland. The presentations will be in the IFW building
(Department for Computer Science). Facilities for slides and computer
demonstrations will be provided.
Other details (registration, travel, lodging, etc.) will come soon.
----------- http://www-calfor.lip6.fr/~wang/ADG2000/index.html ---------------
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 13:48:58 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA23133
for reliable_computing-outgoing; Fri, 12 Nov 1999 13:48:58 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA23128
for ; Fri, 12 Nov 1999 13:48:55 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id NAA14810;
Fri, 12 Nov 1999 13:48:45 -0600 (CST)
Message-Id: <2.2.32.19991112194953.00705c88 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 12 Nov 1999 13:49:53 -0600
To: "Sheela S.(98423301)" ,
reliable_computing [at] interval [dot] usl.edu
From: "R. Baker Kearfott"
Subject: Re: methods with convergence order higher than two
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Sheela,
I believe, for n-th order evaluation of ranges, you need to be
able to get the range of a polynomial of degree n-1 to at least
n-th order. In turn, that job may be difficult. There is an article
by Cornelius and Lohner,
Computing vol. 3 no. 3, pp. 331--347, 1984, entitled
"Computing the Range of Values of Real Functions with Accuracy Higher
than Second Order" that gives insight into this question.
If you get any additional responses, please either post them to
the alias or send them to me, as I am presently also interested
in this question.
Best regards,
Baker
At 12:03 PM 11/12/99 +0530, Sheela S.(98423301) wrote:
>
>Hello,
> I am a Ph.D student working with the applications of IA. Would like to
>know whether there are any methods to construct forms with convergence
>order 3 or 4 for the evaluation of ranges of functions with several
>variables.
>Thanking you in advance,
>sheela
>
>
>--------------------------------------------------------------------------------
>
>Sheela Unnikrishnan (022-5772203)
>Research Scholar, Room No.6,
>Systems & Control Dept QIP Bldg 1
>IIT Bombay, IIT Bombay
>400076. 400076
>India India
>*****************************************************************************|
>
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 14:21:46 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id OAA23502
for reliable_computing-outgoing; Fri, 12 Nov 1999 14:21:46 -0600 (CST)
Received: from pilot021.cl.msu.edu (pilot021.cl.msu.edu [35.9.5.121])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id OAA23497
for ; Fri, 12 Nov 1999 14:21:43 -0600 (CST)
Received: from berz (berz.user.msu.edu [35.10.52.114])
by pilot021.cl.msu.edu (8.9.1a/8.9.1) with SMTP id PAA17618;
Fri, 12 Nov 1999 15:21:14 -0500
From: "Martin Berz"
To: "R. Baker Kearfott" ,
"Sheela S.(98423301)" ,
Subject: RE: methods with convergence order higher than two
Date: Fri, 12 Nov 1999 15:21:05 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
In-Reply-To: <2.2.32.19991112194953.00705c88 [at] pop [dot] usl.edu>
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Sheela, Baker,
the Taylor model method we have been using recently (mostly for verified
integration of ODEs and control of the dependency problem) provides such
inclusions. Specifically, instead of intervals one uses (floating point)
Taylor polynomials with remainder bound and intrinsic operations on these;
the sharpness scales with order (n+1), where n is the order of the
polynomial. In practice we often use multivariate polynomials of orders
between 5 and 20, depending on the complexity of the problem. Some
references are
K. Makino and M. Berz, Remainder Differential Algebras and their
Applications, in: Computational Differentiation: Techniques, Applications,
and Tools,
M. Berz, C. Bischof, G. Corliss and A. Griewank (Eds), SIAM, p.63-74, 1996
M. Berz and G. Hoffstaetter, Computation and Application of Taylor
Polynomials with Interval Remainder Bounds, Reliable Computing 4, p. 83-97,
1998
M. Berz, Differential Algebras with Remainder and Rigorous Proofs of
Long-Term Stability, Fourth Computational Accelerator Physics Conference,
AIP Conference Proceedings vol 391, p. 221, 1996 (a particularly difficult
global optimization problem)
M. Berz and K. Makino, Verified Integration of ODEs and Flows with
Differential Algebraic Methods on Taylor Models, Reliable Computing 4
4, p.361-369, 1998
K. Makino and M. Berz, Efficient Control of the Dependency Problem based on
Taylor Model Methods, Reliable Computing 5, p. 3-12, 1999
M. Berz and K. Makino, New Methods for High-Dimensional Verified Quadrature,
Reliable Computing 5, p. 13-22, 1999
These papers are available for download at bt.nscl.msu.edu/pub. Hope this
helps,
Martin
> -----Original Message-----
> From: owner-reliable_computing [at] interval [dot] usl.edu
> [mailto:owner-reliable_computing [at] interval [dot] usl.edu]On Behalf Of R. Baker
> Kearfott
> Sent: Friday, November 12, 1999 2:50 PM
> To: Sheela S.(98423301); reliable_computing [at] interval [dot] usl.edu
> Subject: Re: methods with convergence order higher than two
>
>
> Sheela,
>
> I believe, for n-th order evaluation of ranges, you need to be
> able to get the range of a polynomial of degree n-1 to at least
> n-th order. In turn, that job may be difficult. There is an article
> by Cornelius and Lohner,
> Computing vol. 3 no. 3, pp. 331--347, 1984, entitled
> "Computing the Range of Values of Real Functions with Accuracy Higher
> than Second Order" that gives insight into this question.
>
> If you get any additional responses, please either post them to
> the alias or send them to me, as I am presently also interested
> in this question.
>
> Best regards,
>
> Baker
>
> At 12:03 PM 11/12/99 +0530, Sheela S.(98423301) wrote:
> >
> >Hello,
> > I am a Ph.D student working with the applications of IA. Would like to
> >know whether there are any methods to construct forms with convergence
> >order 3 or 4 for the evaluation of ranges of functions with several
> >variables.
> >Thanking you in advance,
> >sheela
> >
> >
> >-----------------------------------------------------------------
> ---------------
> >
> >Sheela Unnikrishnan (022-5772203)
> >Research Scholar, Room No.6,
> >Systems & Control Dept QIP Bldg 1
> >IIT Bombay, IIT Bombay
> >400076. 400076
> >India India
> >*****************************************************************
************|
> >
> >
> >
> ---------------------------------------------------------------
> R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
> (337) 482-5270 (work) (337) 981-9744 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
>
>
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 18:06:57 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id SAA23977
for reliable_computing-outgoing; Fri, 12 Nov 1999 18:06:57 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id SAA23972
for ; Fri, 12 Nov 1999 18:06:53 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id RAA01404;
Fri, 12 Nov 1999 17:06:38 -0700 (MST)
Message-Id: <199911130006.RAA01404 [at] cs [dot] utep.edu>
Date: Fri, 12 Nov 1999 17:06:37 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: rbk [at] usl [dot] edu, sheela [at] ee [dot] iitb.ernet.in, reliable_computing [at] interval [dot] usl.edu,
berz [at] msu [dot] edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: daolTAdBwmEwt+n10VMBdg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Martin,
You know I (like many other people) am a great admirer of your results. They
lead to really great applications and interesting theoretical models.
However, with Sheela's question as I understand it, I am not sure that they can
help.
It is my understanding (and I may be wrong) that she is asking about the
following problem:
* given a function f(x1,..,xn) of several variables, and
* a box [l1,u1] x ... x [ln,um]
to compute the range of the function f on a given box with a given accuracy
(e.g., bounded by a given order of the size |ui-li|).
For example, this function f(x1,..,xn) can be a polynomial, e.g., a quadratic
polynomial f(x1,...,xn)=a0+a1*x1+...+an*xn+a11*x1*x1+a12*x1*x2+...+ann*xn*xn
with exactly known coefficients ao, ai, and aij. I do not see how your programs
can help in computing the range of this function on a given box (I give an
example of a quadratic polynomial, because, as I mentioned, computing the range
of a quadratic function with a given accuracy is an NP-hard problem).
By the way, the fact that I do not know how does not mean that it is not
possible, of course. If you know how to use it it will be of great interest.
Vladik
> I am a Ph.D student working with the applications of IA. Would like to
> know whether there are any methods to construct forms with convergence
> order 3 or 4 for the evaluation of ranges of functions with several
> variables.
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 21:23:27 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id VAA24491
for reliable_computing-outgoing; Fri, 12 Nov 1999 21:23:27 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id VAA24486
for ; Fri, 12 Nov 1999 21:23:24 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id VAA19017;
Fri, 12 Nov 1999 21:23:04 -0600 (CST)
Message-Id: <2.2.32.19991113032414.006fbbd8 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 12 Nov 1999 21:24:14 -0600
To: vladik , rbk [at] usl [dot] edu, sheela [at] ee [dot] iitb.ernet.in,
reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Vladik,
Is this NP-complete in the number of variables, in the length of the
description of the function, in both, or in some other item? Can
you post the reference for us? Or has Martin proven P = NP ? My guess
is "no" to the latter. However, his published results do look like an
advance, in some sense.
Baker
At 05:06 PM 11/12/99 -0700, vladik wrote:
>Dear Martin,
>
>You know I (like many other people) am a great admirer of your results. They
>lead to really great applications and interesting theoretical models.
>
>However, with Sheela's question as I understand it, I am not sure that they can
>help.
>
>It is my understanding (and I may be wrong) that she is asking about the
>following problem:
>* given a function f(x1,..,xn) of several variables, and
>* a box [l1,u1] x ... x [ln,um]
>to compute the range of the function f on a given box with a given accuracy
>(e.g., bounded by a given order of the size |ui-li|).
>
>For example, this function f(x1,..,xn) can be a polynomial, e.g., a quadratic
>polynomial f(x1,...,xn)=a0+a1*x1+...+an*xn+a11*x1*x1+a12*x1*x2+...+ann*xn*xn
>with exactly known coefficients ao, ai, and aij. I do not see how your programs
>can help in computing the range of this function on a given box (I give an
>example of a quadratic polynomial, because, as I mentioned, computing the range
>of a quadratic function with a given accuracy is an NP-hard problem).
>
>By the way, the fact that I do not know how does not mean that it is not
>possible, of course. If you know how to use it it will be of great interest.
>
>Vladik
>
>> I am a Ph.D student working with the applications of IA. Would like to
>> know whether there are any methods to construct forms with convergence
>> order 3 or 4 for the evaluation of ranges of functions with several
>> variables.
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 12 21:42:18 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id VAA24797
for reliable_computing-outgoing; Fri, 12 Nov 1999 21:42:18 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id VAA24792
for ; Fri, 12 Nov 1999 21:42:13 -0600 (CST)
Received: (qmail 29504 invoked from network); 13 Nov 1999 04:04:26 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 13 Nov 1999 04:04:26 -0000
Received: from localhost (sheela@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id JAA01752;
Sat, 13 Nov 1999 09:10:17 +0530 (IST)
Date: Sat, 13 Nov 1999 09:10:17 +0530 (IST)
From: "Sheela S.(98423301)"
To: vladik
cc: rbk [at] usl [dot] edu, reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
Subject: RE: methods with convergence order higher than two
In-Reply-To: <199911130006.RAA01404 [at] cs [dot] utep.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Sir,
The functions are irrational and or atan functions with interval
variables. For example [sqrt(1/(x1^2+x2.x3+x1.x3)),atan(x2.x3/(1-x1^2))]
,x1,x2,x3 are intervals.
sheela.
--------------------------------------------------------------------------------
Sheela Unnikrishnan (022-5772203)
Research Scholar, Room No.6,
Systems & Control Dept QIP Bldg 1
IIT Bombay, IIT Bombay
400076. 400076
India India
*****************************************************************************|
On Fri, 12 Nov 1999, vladik wrote:
> Dear Martin,
>
> You know I (like many other people) am a great admirer of your results. They
> lead to really great applications and interesting theoretical models.
>
> However, with Sheela's question as I understand it, I am not sure that they can
> help.
>
> It is my understanding (and I may be wrong) that she is asking about the
> following problem:
> * given a function f(x1,..,xn) of several variables, and
> * a box [l1,u1] x ... x [ln,um]
> to compute the range of the function f on a given box with a given accuracy
> (e.g., bounded by a given order of the size |ui-li|).
>
> For example, this function f(x1,..,xn) can be a polynomial, e.g., a quadratic
> polynomial f(x1,...,xn)=a0+a1*x1+...+an*xn+a11*x1*x1+a12*x1*x2+...+ann*xn*xn
> with exactly known coefficients ao, ai, and aij. I do not see how your programs
> can help in computing the range of this function on a given box (I give an
> example of a quadratic polynomial, because, as I mentioned, computing the range
> of a quadratic function with a given accuracy is an NP-hard problem).
>
> By the way, the fact that I do not know how does not mean that it is not
> possible, of course. If you know how to use it it will be of great interest.
>
> Vladik
>
> > I am a Ph.D student working with the applications of IA. Would like to
> > know whether there are any methods to construct forms with convergence
> > order 3 or 4 for the evaluation of ranges of functions with several
> > variables.
>
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 06:07:48 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id GAA26126
for reliable_computing-outgoing; Sat, 13 Nov 1999 06:07:47 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id GAA26121
for ; Sat, 13 Nov 1999 06:07:44 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id GAA21337;
Sat, 13 Nov 1999 06:07:26 -0600 (CST)
Message-Id: <2.2.32.19991113120832.006fd3d0 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 13 Nov 1999 06:08:32 -0600
To: "Sheela S.(98423301)" ,
vladik
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Cc: reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Sheela,
I suggest you look at Berz' work. It may do the trick for you, depending
on the widths of x1, x2, and x3. One downside: Unless you use Berz'
software, it may take some time to implement.
Best regards,
Baker
At 09:10 AM 11/13/99 +0530, Sheela S.(98423301) wrote:
>Sir,
>The functions are irrational and or atan functions with interval
>variables. For example [sqrt(1/(x1^2+x2.x3+x1.x3)),atan(x2.x3/(1-x1^2))]
>,x1,x2,x3 are intervals.
>sheela.
>--------------------------------------------------------------------------------
>
>Sheela Unnikrishnan (022-5772203)
>Research Scholar, Room No.6,
>Systems & Control Dept QIP Bldg 1
>IIT Bombay, IIT Bombay
>400076. 400076
>India India
>*****************************************************************************|
>
>On Fri, 12 Nov 1999, vladik wrote:
>
>> Dear Martin,
>>
>> You know I (like many other people) am a great admirer of your results. They
>> lead to really great applications and interesting theoretical models.
>>
>> However, with Sheela's question as I understand it, I am not sure that they can
>> help.
>>
>> It is my understanding (and I may be wrong) that she is asking about the
>> following problem:
>> * given a function f(x1,..,xn) of several variables, and
>> * a box [l1,u1] x ... x [ln,um]
>> to compute the range of the function f on a given box with a given accuracy
>> (e.g., bounded by a given order of the size |ui-li|).
>>
>> For example, this function f(x1,..,xn) can be a polynomial, e.g., a quadratic
>> polynomial f(x1,...,xn)=a0+a1*x1+...+an*xn+a11*x1*x1+a12*x1*x2+...+ann*xn*xn
>> with exactly known coefficients ao, ai, and aij. I do not see how your programs
>> can help in computing the range of this function on a given box (I give an
>> example of a quadratic polynomial, because, as I mentioned, computing the range
>> of a quadratic function with a given accuracy is an NP-hard problem).
>>
>> By the way, the fact that I do not know how does not mean that it is not
>> possible, of course. If you know how to use it it will be of great interest.
>>
>> Vladik
>>
>> > I am a Ph.D student working with the applications of IA. Would like to
>> > know whether there are any methods to construct forms with convergence
>> > order 3 or 4 for the evaluation of ranges of functions with several
>> > variables.
>>
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 13:09:36 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA26719
for reliable_computing-outgoing; Sat, 13 Nov 1999 13:09:36 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA26714
for ; Sat, 13 Nov 1999 13:09:13 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id MAA04142;
Sat, 13 Nov 1999 12:08:41 -0700 (MST)
Message-Id: <199911131908.MAA04142 [at] cs [dot] utep.edu>
Date: Sat, 13 Nov 1999 12:08:40 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: vladik [at] cs [dot] utep.edu, rbk [at] usl [dot] edu, sheela [at] ee [dot] iitb.ernet.in,
reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: uXwSknL0NQQVju7XYc7GdA==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
>
> Is this NP-complete in the number of variables, in the length of the
> description of the function, in both, or in some other item? Can
> you post the reference for us? Or has Martin proven P = NP ? My guess
> is "no" to the latter. However, his published results do look like an
> advance, in some sense.
Dear Baker,
I apologize for the confusion.
I have sent the email yesterday, before my reaction
to Martin's posting, with references and explanations, and my reaction to
Martin;s posting was supposed to be a minor comment on my previous emails.
It looks like my previous emails were not received, so I am re-sending them:
*************************************************************************
Dear Sheela, Such forms may exist for particular cases, but in general, it is
impossible; the exact definitions and proofs are given in our paper
Hung T. Nguyen, Vladik Kreinovich, Vyacheslav Nesterov,
and Mutsumi Nakamura,
"On hardware support for interval computations and for
soft computing: a theorem", IEEE Transactions on Fuzzy Systems,
1997, Vol. 5, No. 1, pp. 108-127.
If you have difficulty finding this paper, let me know your mailing address, I
will send you a xerox copy by airmail.
Vladik
P.S. Actually, even for quadratic polynomials, there is no feasible way of
computing the range witha given accuracy (it is an NP-hard problem); see, e.g.,
this result (originally due to Vavasis) is described, among others, in our book
Vladik Kreinovich, Anatoly Lakeyev, Jiri Rohn, and Patrick Kahl,
"Computational complexity and feasibility of
data processing and interval computations",
Kluwer, Dordrecht, 1997.
These negative results do not mean that the situation is all bad: in many
cases, there are methods which work in almost all situations (see same book),
so good practical bounds which are often good are still possible. Vladik
**********************************************************************
Today's comment, and answer to Baker's question: the problem of
computing the range is NP-hard if we allow arbitrary number of
variables; when we fix the number of variables, the problem
can be solved in polynomial time (see our above-cited book),
but the degree of this polynomial grows very rapidly with the
number of variables).
P.P.S. Baker, you seem to say that somewhere in Martin's papers he gives an
algorithm for computing the exact (or good approximate) range of a given
polynomial (to be more precise, he probably talks about a more general problem,
but you seem to imply that it is applicable to a polynomial as well).
Definitely, if you have a function which is NOT a polynomial (as Sheela has)
then Martin;s method can help by reducing it to a polynomial with an arbitrary
degree (the higher the degree, the better the accuracy), but we will still have
the problem of computing the range of a polynomial, the problem which is
NP-hard even when the polynomial is known exactly (and even when it is
quadratic).
It may be that Martin handles the part about computing the range of the
polynomial as well, but I could not find that part. We looked rather
attentively into his papers, because we understand that he does help to solve
differential equations nicely, and we cite that result in our book.
Can you please tell me the exact place where he describes how to find the range
of a give polynomial? I will be glad to look into it.
I am not doubting that it is possible to have an efficient algorithm for
computing the range of a polynomial, since as we have proven in the book (see
above-repeated email), there are polynomial-time alogirthms which compute the
range in almost all cases (in some reasonable sense), I just never looked at
Martin's papers in this way.
Thanks. Vladik
At 05:06 PM 11/12/99 -0700, vladik wrote:
>Dear Martin,
>
>You know I (like many other people) am a great admirer of your results. They
>lead to really great applications and interesting theoretical models.
>
>However, with Sheela's question as I understand it, I am not sure that they
can
>help.
>
>It is my understanding (and I may be wrong) that she is asking about the
>following problem:
>* given a function f(x1,..,xn) of several variables, and
>* a box [l1,u1] x ... x [ln,um]
>to compute the range of the function f on a given box with a given accuracy
>(e.g., bounded by a given order of the size |ui-li|).
>
>For example, this function f(x1,..,xn) can be a polynomial, e.g., a quadratic
>polynomial f(x1,...,xn)=a0+a1*x1+...+an*xn+a11*x1*x1+a12*x1*x2+...+ann*xn*xn
>with exactly known coefficients ao, ai, and aij. I do not see how your
programs
>can help in computing the range of this function on a given box (I give an
>example of a quadratic polynomial, because, as I mentioned, computing the
range
>of a quadratic function with a given accuracy is an NP-hard problem).
>
>By the way, the fact that I do not know how does not mean that it is not
>possible, of course. If you know how to use it it will be of great interest.
>
>Vladik
>
>> I am a Ph.D student working with the applications of IA. Would like to
>> know whether there are any methods to construct forms with convergence
>> order 3 or 4 for the evaluation of ranges of functions with several
>> variables.
>
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 13:46:09 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA27076
for reliable_computing-outgoing; Sat, 13 Nov 1999 13:46:09 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA27071
for ; Sat, 13 Nov 1999 13:46:06 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id NAA23061;
Sat, 13 Nov 1999 13:45:35 -0600 (CST)
Message-Id: <2.2.32.19991113194642.0071fb24 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 13 Nov 1999 13:46:42 -0600
To: vladik , vladik [at] cs [dot] utep.edu, sheela [at] ee [dot] iitb.ernet.in,
reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Vladik,
I did NOT say that Martin gives an algorithm for the exact range of a
polynomial. I am mainly speculating that the Taylor models he espouses
may be more practical than traditional interval computations in many
contexts requiring good bounds on the range. This is not necessarily
in conflict with your complexity results. In particular, my understanding
is that the theory surrounding the Taylor models is an asymptotic
theory, as the widths of the intervals go to zero. However, like
high-order floating-point approximations, the higher-order models may
give better approximations to the range, within wider intervals, than
lower-order models (including plain interval arithmetic).
I must say that I am just now devoting the time they deserve to study
Berz' developments. I will also need to revisit your book to reconcile
the success of the Taylor models with your complexity theory results.
But I don't think there is any contradiction.
Sincerely,
Baker
At 12:08 PM 11/13/99 -0700, vladik wrote:
>
>>**********************************************************************
>Today's comment, and answer to Baker's question: the problem of
>computing the range is NP-hard if we allow arbitrary number of
>variables; when we fix the number of variables, the problem
>can be solved in polynomial time (see our above-cited book),
>but the degree of this polynomial grows very rapidly with the
>number of variables).
>
>P.P.S. Baker, you seem to say that somewhere in Martin's papers he gives an
>algorithm for computing the exact (or good approximate) range of a given
>polynomial (to be more precise, he probably talks about a more general problem,
>but you seem to imply that it is applicable to a polynomial as well).
>
>Definitely, if you have a function which is NOT a polynomial (as Sheela has)
>then Martin;s method can help by reducing it to a polynomial with an arbitrary
>degree (the higher the degree, the better the accuracy), but we will still have
>the problem of computing the range of a polynomial, the problem which is
>NP-hard even when the polynomial is known exactly (and even when it is
>quadratic).
>
>It may be that Martin handles the part about computing the range of the
>polynomial as well, but I could not find that part. We looked rather
>attentively into his papers, because we understand that he does help to solve
>differential equations nicely, and we cite that result in our book.
>
>Can you please tell me the exact place where he describes how to find the range
>of a give polynomial? I will be glad to look into it.
>
>I am not doubting that it is possible to have an efficient algorithm for
>computing the range of a polynomial, since as we have proven in the book (see
>above-repeated email), there are polynomial-time alogirthms which compute the
>range in almost all cases (in some reasonable sense), I just never looked at
>Martin's papers in this way.
>
>Thanks. Vladik
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 14:06:37 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id OAA27390
for reliable_computing-outgoing; Sat, 13 Nov 1999 14:06:18 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id OAA27385
for ; Sat, 13 Nov 1999 14:06:15 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id NAA04320;
Sat, 13 Nov 1999 13:06:07 -0700 (MST)
Message-Id: <199911132006.NAA04320 [at] cs [dot] utep.edu>
Date: Sat, 13 Nov 1999 13:06:06 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: rbk [at] usl [dot] edu
Cc: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 8lxnM9zEJ8+C1fp5LqImSg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Baker,
Thanks for the clarification.
I agree that there is no contradiction between Vavasis's and ours complexity
results and the practical fact that algorithms seem to be often reasonably
efficient: after all, complexity results are about worst-case complexity, and
in practice what we care about is average-case complexity. It is quite possible
(and indeed the case for range computation) that the worst-case complexity is
NP-hard, while the avergae-case complexity is polynomial-time.
I agree 100% that Taylor theory is an asymptotic theory, and as I mentioned in
my yesterday's email, in addition to results about the NP-hardness of exact
range computation, we also have results about NP-hardness of approximnate range
computations with the given accuracy. In addition to these results, in our IEEE
Transaction paper with Nesterov et al which I also cited we give a precise
negative result: that no 3rd or 4th order method is possible for computing the
range (meaning a method which gives this order of accuracy for an arbitrary
polynomial of many variables). (Warning; this paper with Nesterov is one of the
few things which we had to leave out of the book, because we were way above the
original page limit anyway).
I also agree that it may be possible that Taylor-type methods will help in
computing the range (they are definitely helpful in solving differential
equations).
I agree with you that asymptotic methods are likely to produce approximate
result rather than the exact one. All I am saying is that so far, by reading
his papers, I did not find there an algorithm which would compute the range of
a given (exactly known) polynomial with 3rd or 4th order accuracy (which is
what Sheela was asking in the first place).
It may be there. If after studying Martin's papers, you will be able to extract
such an algorithm, please let me know, it will be very helpful. It was so far
my understanding that our book and Martin are about two different problems: we
mainly analyze the complexity of computiung the range of a function, while
Martin is solving differential equations. It could be that I overlooked some
range-computing algorithms which are there as well in his papers.
Any algorithms for solving (some instances of) an NP-hard problem are very
helpful because NP-hardness means that, crudelky speaking, that a given problem
is as hard as problems can be; so any progress in solving one NP_hard problem
can immediately lead to a solution of the others; e.g., in our complexity book,
we show that known good heuristics for solving the range computation problem
lead to new efficient hueristics for another NP-hard problem - propositional
satisfiability. In this sense, any new algorithm for solving a problem which
is, in general, NP-hard, is of great interest.
Thanks.
Vladik
> X-Sender: rbk5287 [at] pop [dot] usl.edu
> Mime-Version: 1.0
> Date: Sat, 13 Nov 1999 13:46:42 -0600
> To: vladik , vladik [at] cs [dot] utep.edu, sheela [at] ee [dot] iitb.ernet.in,
reliable_computing [at] interval [dot] usl.edu, berz [at] msu [dot] edu
> From: "R. Baker Kearfott"
> Subject: RE: methods with convergence order higher than two
>
> Vladik,
>
> I did NOT say that Martin gives an algorithm for the exact range of a
> polynomial. I am mainly speculating that the Taylor models he espouses
> may be more practical than traditional interval computations in many
> contexts requiring good bounds on the range. This is not necessarily
> in conflict with your complexity results. In particular, my understanding
> is that the theory surrounding the Taylor models is an asymptotic
> theory, as the widths of the intervals go to zero. However, like
> high-order floating-point approximations, the higher-order models may
> give better approximations to the range, within wider intervals, than
> lower-order models (including plain interval arithmetic).
>
>
> I must say that I am just now devoting the time they deserve to study
> Berz' developments. I will also need to revisit your book to reconcile
> the success of the Taylor models with your complexity theory results.
> But I don't think there is any contradiction.
>
> Sincerely,
>
> Baker
>
> At 12:08 PM 11/13/99 -0700, vladik wrote:
> >
> >>**********************************************************************
> >Today's comment, and answer to Baker's question: the problem of
> >computing the range is NP-hard if we allow arbitrary number of
> >variables; when we fix the number of variables, the problem
> >can be solved in polynomial time (see our above-cited book),
> >but the degree of this polynomial grows very rapidly with the
> >number of variables).
> >
> >P.P.S. Baker, you seem to say that somewhere in Martin's papers he gives an
> >algorithm for computing the exact (or good approximate) range of a given
> >polynomial (to be more precise, he probably talks about a more general
problem,
> >but you seem to imply that it is applicable to a polynomial as well).
> >
> >Definitely, if you have a function which is NOT a polynomial (as Sheela has)
> >then Martin;s method can help by reducing it to a polynomial with an
arbitrary
> >degree (the higher the degree, the better the accuracy), but we will still
have
> >the problem of computing the range of a polynomial, the problem which is
> >NP-hard even when the polynomial is known exactly (and even when it is
> >quadratic).
> >
> >It may be that Martin handles the part about computing the range of the
> >polynomial as well, but I could not find that part. We looked rather
> >attentively into his papers, because we understand that he does help to
solve
> >differential equations nicely, and we cite that result in our book.
> >
> >Can you please tell me the exact place where he describes how to find the
range
> >of a give polynomial? I will be glad to look into it.
> >
> >I am not doubting that it is possible to have an efficient algorithm for
> >computing the range of a polynomial, since as we have proven in the book
(see
> >above-repeated email), there are polynomial-time alogirthms which compute
the
> >range in almost all cases (in some reasonable sense), I just never looked at
> >Martin's papers in this way.
> >
> >Thanks. Vladik
> >
>
> ---------------------------------------------------------------
> R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
> (337) 482-5270 (work) (337) 981-9744 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
>
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 14:43:40 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id OAA27777
for reliable_computing-outgoing; Sat, 13 Nov 1999 14:43:40 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id OAA27772
for ; Sat, 13 Nov 1999 14:43:38 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id OAA23531;
Sat, 13 Nov 1999 14:43:21 -0600 (CST)
Message-Id: <2.2.32.19991113204427.00724250 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 13 Nov 1999 14:44:27 -0600
To: vladik
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Cc: reliable_computing [at] interval [dot] usl.edu
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Vladik,
I was reading
M. Berz and G. Hoffstaetter, "Computation and Application of Taylor Polynomials with
Interval Remainder Bounds," "Reliable Computing" 4:83-97 (1998). The last sentence
of the abstract says "The method is used for guaranteed global optimization
of blow-up prone functions." Also, in the introduction, it describes a typical
interval global optimization algorithm that fails because of overestimation
in the range of the function. This led me to believe that a better method of
bounding the range would be presented.
Also, in Makino and Berz, "Efficient Control of The Dependency Problem
Based on Taylor Model Methods", "Reliable Computing" 5:3-12, 1999, an example of
a range enclosure using both a traditional interval method and using
the Taylor model is given on pp. 6-7. There, the Taylor model gives an essentially
sharp enclosure of the range from order 5 on.
However, examining the Berz and Hoffstaetter paper, I see that the Taylor model
gives a bound on the function values at any POINT in the interval of approximation,
whereas how the authors obtained the bounds on the function over the BOXES
in the Makino/Berz paper was not described, except to say that Taylor models were
used. (Clearly, plugging intervals into the argument of the Taylor model won't
work in general, as it doesn't give higher than a second-order enclosure.)
Also, in the Berz/Hoffstaetter paper, the global optimization problem
solved was a special problem related to beam physics, and involving a "transfer
function". Without digging back to previous work on this (Interval Computations
1994 no. 2), I suspect that special techniques were used that cannot be used
in general to bound the range of any Taylor model.
Thus, I have questions about using Taylor models to bound the range of
functions over entire intervals. Martin, can you clarify?
Baker
At 01:06 PM 11/13/99 -0700, vladik wrote:
>Dear Baker,
>
>I also agree that it may be possible that Taylor-type methods will help in
>computing the range (they are definitely helpful in solving differential
>equations).
>
>I agree with you that asymptotic methods are likely to produce approximate
>result rather than the exact one. All I am saying is that so far, by reading
>his papers, I did not find there an algorithm which would compute the range of
>a given (exactly known) polynomial with 3rd or 4th order accuracy (which is
>what Sheela was asking in the first place).
>
>It may be there. If after studying Martin's papers, you will be able to extract
>such an algorithm, please let me know, it will be very helpful. It was so far
>my understanding that our book and Martin are about two different problems: we
>mainly analyze the complexity of computiung the range of a function, while
>Martin is solving differential equations. It could be that I overlooked some
>range-computing algorithms which are there as well in his papers.
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 15:24:52 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id PAA28144
for reliable_computing-outgoing; Sat, 13 Nov 1999 15:24:52 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id PAA28139
for ; Sat, 13 Nov 1999 15:24:41 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id OAA04497;
Sat, 13 Nov 1999 14:24:31 -0700 (MST)
Message-Id: <199911132124.OAA04497 [at] cs [dot] utep.edu>
Date: Sat, 13 Nov 1999 14:24:30 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: vladik [at] cs [dot] utep.edu, rbk [at] usl [dot] edu
Cc: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 1u1SC1w3tPiLH7uuCgDL0w==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Baker,
I think that this discussion is very useful because it attracts the
participants' attention to Martin's very important algorithms. Thanks for the
references. I have read the papers again, and now I understand hopefully the
situation better.
I want to present my understanding in the form that Martin and I are both right
(actually, Martin is more right that I am, because
* I am right formally, while
* he is right in reality).
Here is my explanation.
As I understand it, Martin's idea of computing the range as described in his
paper with Makino (Vol. 5 of Relibale Computing) is as follows:
* Let us assume that we have a function f(x1,...,xn) which may
include trigonometric and other special functions.
* If we use naive interval computations to estimate the range
of this function on a small box, we may get a big overestimation.
* Instead of applying naive interval computations (or centered method,
or any other known technique), we
* first apply Taylor method and
find the Taylor expansion of the given function in the vicinity
of the given point (the center of the small box on which we want
to estimate the range), i.e., a polynomial P(x1,...,xn) together
with the interval which estimates the remainder.
The difference
between f and P can be made as small as possible: we can have
3rd, 4th, 12th order etc. methods depending on how many terms we
preserve in the Taylor expansion
* Then, we apply naive interval computations or any other known
techniques (centered, etc.) to estimate the range of the polynomial
* After that, add the interval for the remainder to get the final
enclosure.
On the estimate-polynomial's-range step, we get an NP-hard problem for which it
is impossible to have an estimate which is always of 3rd order (see our paper
with Slava). As a result, the total order of the two-step procedure cannot be
3rd order, so formally speaking, my answer is right that there is no 3rd order
procedure which can help.
In particular, when we start with a quadratic polynomial in the first place
(and this problem is NP-hard for quadratic polynomials already), Taylor's
approximation is exact, so there is no remainder at all (the approximation of f
by P is accuracy with 3rd, 4th, etc., any degree). However, in this particular
case, Martin's method does not give us any new estimate for the range: it
simply says that we have to use the estimate for the original polynomial.
For most small sub-boxes of the original box, the function P will be monotonic
in all the variables, so we can get the exact estimate. In a few points where
the derivatives are close to 0 we may have an overestimation, and this
overestimation may be of 2nd order. This explains in what sense I am right.
On the other hand, Martin was absolutely right because he understood Sheela's
question not as
* a formal question on whether 3rd and 4th order metjods are possible, but as
* a practical question on how to best estimate the range.
The function that Sheela has in mind is exactly the type to which Martin's
method is applied. In this case, if
* instead of applying interval computation techniques to the original
expression,
* we first replace it with its Taylor series,
we will most probably get a much better estimate (although if we take the error
of estimating the range of the polynomial P into consideration, this estimate
will not be necessarily of 3rd or 4th order).
Summarizing:
* Martin is more right: from the practical viewpoint, by using his method,
we get a better estimate for the range, and the first part of the error
(approximating f by a polynomial P) can be made 3rd order, 4th order etc.
* I am also right (theoretically) because although Martin's method will
probably lead to a good estimate, we will not necessarily get the
estimate of a range which is of 3rd order in terms of the widths of the
original intervals, because the second part of his algorithm
(estimating the range of the polynomial) may lead to larger errors.
So:
* theoretically, unless there is an error in our paper, I believe we
are right literally, in the sense that no 3rd order method of
estimating the range of the function is possible;
* in practice, however, Maryin is right, because a very good
approximation method is possible, and in some sense (namely,
if we only consider the error of the first step) it is of 3rd order.
If, as I understand it, Sheela really wants to compute the range nicely, then
we should accept the fact that it is theoretically impossible to get a range
which is 3rd order estimate and use the best possible known algorithm (Martin's
may as well be a one) for which at least the first component of the error is
3rd order.
Vladik
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 13 18:32:08 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id SAA28606
for reliable_computing-outgoing; Sat, 13 Nov 1999 18:32:08 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id SAA28601
for ; Sat, 13 Nov 1999 18:31:49 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id SAA25043;
Sat, 13 Nov 1999 18:31:34 -0600 (CST)
Message-Id: <2.2.32.19991114003241.0074ed8c [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 13 Nov 1999 18:32:41 -0600
To: vladik , vladik [at] cs [dot] utep.edu
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Cc: reliable_computing [at] interval [dot] usl.edu
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Vladik,
Yes, true. However, I'd still like to hear from Berz et al about the
details of estimating the range of the polynomial. In particular, the
numerical results on pp. 6-7 of Reliable Computing 5(1), February, 1999
are impressive, but details of the computation were not given.
Best regards,
Baker
At 02:24 PM 11/13/99 -0700, vladik wrote:
>Dear Baker,
>
>I think that this discussion is very useful because it attracts the
>participants' attention to Martin's very important algorithms. Thanks for the
>references. I have read the papers again, and now I understand hopefully the
>situation better.
>
>I want to present my understanding in the form that Martin and I are both right
>(actually, Martin is more right that I am, because
>* I am right formally, while
>* he is right in reality).
>Here is my explanation.
>
>As I understand it, Martin's idea of computing the range as described in his
>paper with Makino (Vol. 5 of Relibale Computing) is as follows:
>* Let us assume that we have a function f(x1,...,xn) which may
> include trigonometric and other special functions.
>* If we use naive interval computations to estimate the range
> of this function on a small box, we may get a big overestimation.
>* Instead of applying naive interval computations (or centered method,
> or any other known technique), we
> * first apply Taylor method and
> find the Taylor expansion of the given function in the vicinity
> of the given point (the center of the small box on which we want
> to estimate the range), i.e., a polynomial P(x1,...,xn) together
> with the interval which estimates the remainder.
>
> The difference
> between f and P can be made as small as possible: we can have
> 3rd, 4th, 12th order etc. methods depending on how many terms we
> preserve in the Taylor expansion
> * Then, we apply naive interval computations or any other known
> techniques (centered, etc.) to estimate the range of the polynomial
> * After that, add the interval for the remainder to get the final
> enclosure.
>
>On the estimate-polynomial's-range step, we get an NP-hard problem for which it
>is impossible to have an estimate which is always of 3rd order (see our paper
>with Slava). As a result, the total order of the two-step procedure cannot be
>3rd order, so formally speaking, my answer is right that there is no 3rd order
>procedure which can help.
>
>In particular, when we start with a quadratic polynomial in the first place
>(and this problem is NP-hard for quadratic polynomials already), Taylor's
>approximation is exact, so there is no remainder at all (the approximation of f
>by P is accuracy with 3rd, 4th, etc., any degree). However, in this particular
>case, Martin's method does not give us any new estimate for the range: it
>simply says that we have to use the estimate for the original polynomial.
>
>For most small sub-boxes of the original box, the function P will be monotonic
>in all the variables, so we can get the exact estimate. In a few points where
>the derivatives are close to 0 we may have an overestimation, and this
>overestimation may be of 2nd order. This explains in what sense I am right.
>
>On the other hand, Martin was absolutely right because he understood Sheela's
>question not as
>* a formal question on whether 3rd and 4th order metjods are possible, but as
>* a practical question on how to best estimate the range.
>The function that Sheela has in mind is exactly the type to which Martin's
>method is applied. In this case, if
>* instead of applying interval computation techniques to the original
> expression,
>* we first replace it with its Taylor series,
>we will most probably get a much better estimate (although if we take the error
>of estimating the range of the polynomial P into consideration, this estimate
>will not be necessarily of 3rd or 4th order).
>
>Summarizing:
>* Martin is more right: from the practical viewpoint, by using his method,
> we get a better estimate for the range, and the first part of the error
> (approximating f by a polynomial P) can be made 3rd order, 4th order etc.
>
>* I am also right (theoretically) because although Martin's method will
> probably lead to a good estimate, we will not necessarily get the
> estimate of a range which is of 3rd order in terms of the widths of the
> original intervals, because the second part of his algorithm
> (estimating the range of the polynomial) may lead to larger errors.
>
>So:
>* theoretically, unless there is an error in our paper, I believe we
> are right literally, in the sense that no 3rd order method of
> estimating the range of the function is possible;
>* in practice, however, Maryin is right, because a very good
> approximation method is possible, and in some sense (namely,
> if we only consider the error of the first step) it is of 3rd order.
>
>If, as I understand it, Sheela really wants to compute the range nicely, then
>we should accept the fact that it is theoretically impossible to get a range
>which is 3rd order estimate and use the best possible known algorithm (Martin's
>may as well be a one) for which at least the first component of the error is
>3rd order.
>
>Vladik
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 14 08:02:40 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id IAA29601
for reliable_computing-outgoing; Sun, 14 Nov 1999 08:02:40 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id IAA29596
for ; Sun, 14 Nov 1999 08:02:37 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id IAA28885;
Sun, 14 Nov 1999 08:02:28 -0600 (CST)
Message-Id: <2.2.32.19991114140337.03898678 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sun, 14 Nov 1999 08:03:37 -0600
To: reliable_computing [at] interval [dot] usl.edu, validated_numerics@tu-harburg.de,
interval [at] cs [dot] utep.edu
From: "R. Baker Kearfott"
Subject: Mailing list for intervals in Fortran
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Colleagues,
As you have previously been informed (see the attached message
below), Sun has released its beta test version of its Fortran 95
compiler, that has a fast intrinsic interval data type. (A standard
function interval evaluation takes 1.8 times the time of a corresponding
floating point evaluation, and extended interval arithmetic is
built-in for non-stop operation. Also, combined with standard-conforming
features of Fortran 95, interval matrix and array operations, etc. are
available, as well as derived-type operator overloading with intervals
as the base type.)
To discuss interval arithmetic issues users encounter while using this
compiler, I have set up a mailing list. Anyone can send questions
to this list. To participate in resolving such questions, you may
subscribe to the list. To subscribe to the list, send mail to
majordomo [at] interval [dot] usl.edu
and include the line
subscribe sun-interval-fortran-questions
in the body. To get a complete list of commands available, send mail
to majordomo [at] interval [dot] usl.edu, and include the line
help
in the body.
To send questions or comments to the subscribers, send your message to
sun-interval-fortran-questions [at] interval [dot] usl.edu
Postings to this list are archived.
Best regards,
Baker
==========================================================================
>Return-Path:
>Date: Tue, 09 Nov 1999 11:30:53 -0800 (PST)
>From: William Walster
>Subject: Sun f95 Early Access with Interval Support
>To: reliable_computing [at] interval [dot] usl.edu, validated_numerics@tu-harburg.de,
> interval [at] cs [dot] utep.edu
>Reply-to: William Walster
>Content-MD5: u8tMKxhUhtS+oICOt/QD1A==
>Sender: owner-reliable_computing [at] interval [dot] usl.edu
>
>
>
>Dear members of the Interval Community:
>
>The early access (beta test) version of Sun's Fortran 95 compiler with
>support for intrinsic interval data types is now available. See:
>
> http://access1.sun.com/workshop6ea/
>
>This is a major accomplishment, to which many in the interval community
>have contributed. Thanks!
>
>Commercial interval support provides a number of opportunities for members
>of the interval community and for Sun. Members of the interval community
>have an important role to play in helping to make sure support for intervals
>is a commercial success. If it is, both the interval community and
>Sun will benefit.
>
>Because intervals are still new to most of the computing world, and because
>some new interval support functionality is being introduced in the f95
>compiler, customer support may be an issue. Sun can't undertake a wholesale
>education effort on the methods and benefits of interval arithmetic right now;
>getting the existing capabilities known and used is the immediate goal. To
>help with the education effort, support from the interval community will be
>beneficial to all concerned. Most importantly, it will help those new to
>intervals to get questions answered and to be able to access as many existing
>interval programs as possible:
>
> a) so they don't have to reinvent these codes; and
>
> b) so they can see how well constructed interval algorithms are
> developed, implemented and tested using the f95 compiler.
>
>The following plan is designed to maximize our collective upside opportunity.
>
>Early access is scheduled run for 16 weeks. In the first phase, it will be
>helpful to keep access to Fortran developers in the interval community.
>Feedback, both about bugs and the content of draft documentation will be
>most helpful.
>
>Feedback will be facilitated by an email alias within which EA participants
>can discuss problems/issues/concerns, and where possible solutions
>can be reviewed. I hope there will be few if any controversies. If any
>develop, it will be helpful to confine them to this alias, until they can
>be constructively resolved.
>
>Once through the first phase and any serious problems are resolved, we
>can invite more members of the interval community, companies, and
>researchers to participate more fully. At this point, it will be critical
>for members of the interval community help support those users who are new
>to intervals. Sun's resources will be best spent analyzing and fixing
>whatever problems are uncovered. If interval community support can
>continue after the compiler ships, it will benefit all concerned. A
>positive response to intervals and the compiler can be leverage for
>additional funding of interval cooperative research and development,
>from which more end-user applications can be developed.
>
>In parallel with the above, it will also be helpful if as much
>existing interval code as possible is ported onto the f95 compiler. This
>should be a relatively easy. Posting these codes and libraries to the
>Internet will provide new users with existing routines to use and from
>which they can clone and build their own routines. If these codes, test
>cases, and documentation can be posted to the Internet, Sun will be able
>to incorporate them into its application test suites. If documentation
>is available in published books or manuscripts, pointers to them will be
>helpful. This will be a good opportunity for the excellent work done at
>many universities and Professor Kulisch's institute to get wide exposure.
>
>Please let me know if there are any other suggestions you have that
>will help make this interval product rollout successful, both for
>the interval community and for Sun.
>
>Thanks in advance for your help and support,
>
>Bill
>
> G. William (Bill) Walster, Ph.D.
> Interval Technology Engineering Manager
> Sun Microsystems, Inc.
> 901 San Antonio Road, MS UMPK16-304
> Palo Alto, CA 94303-4900
> (650) 786-9004 Direct
> (650) 786-9551 Fax
> bill.walster [at] eng [dot] sun.com
>
>P.S. Look for us at SC99 in Portland.
>
>
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 14 13:56:53 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA00399
for reliable_computing-outgoing; Sun, 14 Nov 1999 13:56:53 -0600 (CST)
Received: from pilot021.cl.msu.edu (pilot021.cl.msu.edu [35.9.5.121])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA00394
for ; Sun, 14 Nov 1999 13:56:30 -0600 (CST)
Received: from berz (pm529-29.dialip.mich.net [35.9.48.181])
by pilot021.cl.msu.edu (8.9.1a/8.9.1) with SMTP id OAA76774;
Sun, 14 Nov 1999 14:56:01 -0500
From: "Martin Berz"
To: "vladik" ,
Cc: ,
"Makino Kyoko (NSCL)"
Subject: RE: methods with convergence order higher than two
Date: Sun, 14 Nov 1999 14:55:51 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
In-Reply-To: <199911132124.OAA04497 [at] cs [dot] utep.edu>
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Baker, Vladik, Sheela,
now I had taken off Saturday, and found out that I apparently missed
something interesting - sorry for keeping people waiting, let me try to
address some of the points now. Actually this is a good example of the nice
job that Interval people, and in particular Baker and Vladik, are doing
about getting to the bottom of may interval-related topics in this useful
discussion server.
By the time I am now re-entering the discussion, quite a few aspects have
been touched upon, and I am basing my answer mostly on Vladik's last email
because it attempts to summarize many of the points and hence allows me to
insert my answers in perhaps a most structured way. In addition, I will try
to interweave other questions that seem to have come up by Baker and Sheela;
if I may have missed something, please ask again. Please note, however, that
because of a commitment this Sunday afternoon, I may not be able to reply
before Monday ( perhaps I have to re-think the amount of dedication to my
work ;-)... ) To close the introduction, Vladik, can you send me a paper or
.ps copy of your IEEE complexity paper?
Martin
> -----Original Message-----
> From: owner-reliable_computing [at] interval [dot] usl.edu
> [mailto:owner-reliable_computing [at] interval [dot] usl.edu]On Behalf Of vladik
> Sent: Saturday, November 13, 1999 4:25 PM
> To: vladik [at] cs [dot] utep.edu; rbk [at] usl [dot] edu
> Cc: reliable_computing [at] interval [dot] usl.edu
> Subject: RE: methods with convergence order higher than two
>
>
> Dear Baker,
>
> I think that this discussion is very useful because it attracts the
> participants' attention to Martin's very important algorithms.
> Thanks for the
> references. I have read the papers again, and now I understand
> hopefully the
> situation better.
>
> I want to present my understanding in the form that Martin and I
> are both right
> (actually, Martin is more right that I am, because
> * I am right formally, while
> * he is right in reality).
> Here is my explanation.
>
> As I understand it, Martin's idea of computing the range as
> described in his
> paper with Makino (Vol. 5 of Relibale Computing) is as follows:
> * Let us assume that we have a function f(x1,...,xn) which may
> include trigonometric and other special functions.
> * If we use naive interval computations to estimate the range
> of this function on a small box, we may get a big overestimation.
> * Instead of applying naive interval computations (or centered method,
> or any other known technique), we
> * first apply Taylor method and
> find the Taylor expansion of the given function in the vicinity
> of the given point (the center of the small box on which we want
> to estimate the range), i.e., a polynomial P(x1,...,xn) together
> with the interval which estimates the remainder.
This is correct. To clarify, we are using floating-point Taylor
coefficients; and furthermore it is very important to calculate the
remainder bound in parallel with the multivariate Taylor polynomial. One
could, in principle, also use high-order AD to shove the domain through the
respective (n+1)st order derivatives, but this actually leads to much more
pessimistic results because of cancellation etc etc.
>
> The difference
> between f and P can be made as small as possible: we can have
> 3rd, 4th, 12th order etc. methods depending on how many terms we
> preserve in the Taylor expansion
True, down to some reasonable multiple of the "accuracy floor" of your
floating point environment. The method will stabilize there, since
eventually floating point errors in the Taylor coefficient calculation
(which are lumped into the remainder bound) will take over and start
dominating things.
> * Then, we apply naive interval computations or any other known
> techniques (centered, etc.) to estimate the range of the polynomial
Yes, we estimate the range of the polynomial, and we COULD do that with
naive intervals, centered form etc, or an off-the-shelf general range
bounder like Baker's. However, because of the basic algorithm, the
polynomials that occur have very special structure: their contribution
decreases rapidly with order. For if this is not the case, the high-order
Taylor approximation doesn't produce a sharp remainder - it's like being
outside the range of convergence of Newton's method, to use a second order
analogy. This is the key point why the polynomial can be done efficiently,
and also why we are as far as I can see not in the terrain where the normal
complexity statements have bearing. I will provide more detail below
connected to the more concise question from Baker, and keep going for now in
order to not interrupt the flow of Vladik's summary too much.
> * After that, add the interval for the remainder to get the final
> enclosure.
>
True. And clarifying Baker's comment, it is indeed bounding over boxes, not
point evaluations, that we are considering here. Also, it doesn't rest on
special assumptions on the transfer function (in fact, the earlier work from
1994 that Baker quotes did do that in an interesting way - but let me not
get into details about that here). Finally, Sheela, the functions you
describe are in the class we studying with the methods.
> On the estimate-polynomial's-range step, we get an NP-hard
> problem for which it
> is impossible to have an estimate which is always of 3rd order
> (see our paper
> with Slava). As a result, the total order of the two-step
> procedure cannot be
> 3rd order, so formally speaking, my answer is right that there is
> no 3rd order
> procedure which can help.
>
> In particular, when we start with a quadratic polynomial in the
> first place
> (and this problem is NP-hard for quadratic polynomials already), Taylor's
> approximation is exact, so there is no remainder at all (the
> approximation of f
> by P is accuracy with 3rd, 4th, etc., any degree). However, in
> this particular
> case, Martin's method does not give us any new estimate for the range: it
> simply says that we have to use the estimate for the original polynomial.
Yes in the sense that there is no remainder bound, and we are faced with the
task of bounding the polynomial just as before. But besides, the algorithms
detects whether the polynomial is favorable for the method to work (i.e.
with sufficiently rapidly decreasing high-order contributions), or whether
we may have to narrow the original domain box. As a consequence, our
polynomial bounder gets invoked only in the favorable case.
>
> For most small sub-boxes of the original box, the function P will
> be monotonic
> in all the variables, so we can get the exact estimate. In a few
> points where
> the derivatives are close to 0 we may have an overestimation, and this
> overestimation may be of 2nd order. This explains in what sense I
> am right.
>
I think Vladik's thoughts go essentially in the right direction; while the
function doesn't have to be monotonic, the criterion is that it must be of
the form that the orders in the Taylor expansion converge quickly enough. In
algorithmic practice, this aspect is actually checked at many places as we
go through the code. And whenever doing Taylor models, you may want to
carry along a naive interval estimator in parallel as well; if one has such
large domains where high-order Taylor doesn't work anymore (and because of
the high-order behavior, Taylor may actually be worse than naive
intervals), then the algorithm falls back to lower order Taylor, or even
regular intervals.
This is actually rather similar in flavor to a step size controller in a
numeric integrator, where often essentially two algorithms of different
order are run against each other, and the difference is used as a measure of
accuracy; which merely means that the high orders fall of fast enough. Using
this diagnostic, one doesn't loose time for needless Taylor calculations
(except for the first diagnostis of "trouble"), and is guaranteed to always
do at least as well as naive interval. But in addition one has a reasonable
estimate of how good (or rather, bad) the interval result is to be expected
to be, which can be used in the branch-and-bound controller. In practice, of
course once you reach a certain threshold, Taylor has a tendency to take
over very beneficially.
> On the other hand, Martin was absolutely right because he
> understood Sheela's
> question not as
> * a formal question on whether 3rd and 4th order metjods are
> possible, but as
> * a practical question on how to best estimate the range.
> The function that Sheela has in mind is exactly the type to which
> Martin's
> method is applied. In this case, if
> * instead of applying interval computation techniques to the original
> expression,
> * we first replace it with its Taylor series,
> we will most probably get a much better estimate
basically yes.
(although if we
> take the error
> of estimating the range of the polynomial P into consideration,
> this estimate
> will not be necessarily of 3rd or 4th order).
Now let us see about the polynomial bounding. As alluded above, it rests on
the fact of sufficiently rapid decrease with order; as such, it is not
applicable to the general polynomial bounding problem (unless of course you
first allow to split the boxes over which these are needed so they become
sufficently small, the diagnostic of which with centered form etc goes
quadratic - so no problem with the complexity theory here). The question
about dedicated polynomial bounders in general was actually posed a few
months ago on this discussion board, but I didn't provide a remark because
our case is of course special. From Vladik's complexity point of view, it
would be somewhat interesting whether
1) this essential phenomenon of "rapidly decreasing order" can be described
somewhat rigorously within the framework of complexity, and if this is the
case,
2) whether there are any known scaling laws for this particular case.
Be this as it may, here is how our algorithm for polynomials with rapidly
decreasing order works:
1) First, split the polynomial into a (low-order) part L for which we can
determine location of points that provide maxima exactly, and the high-order
rest H for which we cannot. For example, if L ist just the linear part, it
can be bounded exactly, and the maximum always occurs in one of the corners
in the multidimensional box, and it's even very cheap, with essentially no
penalty for higher orders. Second order L (with fixed variable numbers - see
Vladik's comment on complexity as function of number of variables) can be
done reasonably easily for any number of variables; to this end, consider
the edges, which gives second order of one degree less (and then iterate),
and look on the inside which gives a linear system via vanishing gradient.
To higher orders of L, I will come back below, in the framework of
complexity discussions.
2) Next determine a crude bound B(H) for H over the entire box (e.g. by
naive intervals etc; in fact, in our Taylor model arithmetic, we obtain
these sharper than with regular intervals as a free by-product).
3) Looking at the exact maximizing points of L and the crude higher order
bound B(H), and the fact that the L dominates the behavior since by
definition high orders are assumed to decrease quickly, one can shrink the
box over which the maximum occurs. For L linear, the size is determined by
something like B(H) / B(grad L), and we have quadratic convergence. For L
second order it's cubic, etc.
In practice, this polynomial bound works nicely, and compared to the large
amount of floating point arithmetic going into the Taylor coefficient
calculations (which we note doesn't have to be iterated), the polynomial
bounding doesn't contribute so significantly to the effort. So for practical
purposes, performance is usually dominated by the desired order of the
Taylor model, not the polynomial bounder.
>
> Summarizing:
> * Martin is more right: from the practical viewpoint, by using his method,
> we get a better estimate for the range, and the first part of the error
> (approximating f by a polynomial P) can be made 3rd order, 4th
> order etc.
>
> * I am also right (theoretically) because although Martin's method will
> probably lead to a good estimate, we will not necessarily get the
> estimate of a range which is of 3rd order in terms of the widths of the
> original intervals, because the second part of his algorithm
> (estimating the range of the polynomial) may lead to larger errors.
>
I believe that is true if we consider all possible scenarios for ranges;
currenly of course the accuracy requirement for the polynomial bounder is
controlled by the accuracy of the remainder bound (there is no point getting
the polynomial bounded say more than 10 times sharper than the remainder
bound), which throws a somewhat ugly termination criterion in the
theoretical study of algorithmic performance. Nevertheless, while for a many
typically occuring ranges it works very nicely, it may break down
asymptotically. Two scenarios:
1) For too large domains outside the range of "orders decreasing quickly",
the Taylor remainder bound becomes extremely pessimistic, and you loose with
order (n+1) ... No need for sharp polynomial bounding anymore, but you are
dead nonetheless.
2) For extremely small domains, assuming an "accuracy floor" substantially
below what we typically have for floating point, we may get so extremely
tiny remainder bounds scaling with order (n+1) that the polynomial bounder
has a very hard time to reach a similar sharpness.
> So:
> * theoretically, unless there is an error in our paper, I believe we
> are right literally, in the sense that no 3rd order method of
> estimating the range of the function is possible;
Vladik, let me ask the following: suppose I have a fifth order polynomial P
of one variable, to bound over the range [a,b]. I can do this by freshman
math by calculating the zeros of the derivative (for which there is a closed
formula; perhaps sophomore math, but nonetheless) Then I throw out those
critical points that lie outside [a,b] and evaluate the function at the at
most 6 total points consisting of surviving boundary points and a and b to
get the range. Altogether, the only part of the algorithm that depends on
[a,b] at all is the exclusion of irrelevant critical points; but while the
computation of bounds takes longer for big [a,b] because there may be more
critical points inside, the bounds are exact (to floating point etc etc).
Isn't this a scaling with the accuracy that is higher than second order?
While of course this fifth order polynomial is highly hypothetical for the
general function case, it does appear in the fifth order one variable Taylor
model problem.
> * in practice, however, Maryin is right, because a very good
> approximation method is possible, and in some sense (namely,
> if we only consider the error of the first step) it is of 3rd order.
>
> If, as I understand it, Sheela really wants to compute the range
> nicely, then
> we should accept the fact that it is theoretically impossible to
> get a range
> which is 3rd order estimate and use the best possible known
> algorithm (Martin's
> may as well be a one) for which at least the first component of
> the error is
> 3rd order.
>
> Vladik
>
>
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 14 16:33:26 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id QAA00855
for reliable_computing-outgoing; Sun, 14 Nov 1999 16:33:26 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id QAA00850
for ; Sun, 14 Nov 1999 16:33:23 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id PAA07774;
Sun, 14 Nov 1999 15:33:13 -0700 (MST)
Message-Id: <199911142233.PAA07774 [at] cs [dot] utep.edu>
Date: Sun, 14 Nov 1999 15:33:12 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: vladik [at] cs [dot] utep.edu, rbk [at] usl [dot] edu, berz [at] msu [dot] edu
Cc: reliable_computing [at] interval [dot] usl.edu, makino [at] nscl [dot] msu.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 1dZkdxJ+l/4PgxUAukTkuw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Martin,
Thanks a lot for the detailed answer. I am glad that we are very much in
agreement, and that my understanding of your text is essentially correct.
Thanks for your interest in our results on complexity. I have just sent you a
PS file with our paper w/Nesterov, and if necessary, I will be glad to send you
a copy of the corresponding part of our complexity book (if you do not have
easy access ot it).
The only point which requires clarification is computing the exact bounds for a
quadratic polynomial. This problem is NPhard (result by Vavasis, mentioned and
proven in our book). Of course, we can explicitly compute it but this
computation will require the time which grows exponentially with the number of
variables, so it is 2^n.
> 1) First, split the polynomial into a (low-order) part L for which we can
> determine location of points that provide maxima exactly, and the high-order
> rest H for which we cannot. For example, if L ist just the linear part, it
> can be bounded exactly, and the maximum always occurs in one of the corners
> in the multidimensional box, and it's even very cheap, with essentially no
> penalty for higher orders. Second order L (with fixed variable numbers - see
> Vladik's comment on complexity as function of number of variables) can be
> done reasonably easily for any number of variables; to this end, consider
> the edges, which gives second order of one degree less (and then iterate),
> and look on the inside which gives a linear system via vanishing gradient.
> To higher orders of L, I will come back below, in the framework of
> complexity discussions.
A similar issue:
> Vladik, let me ask the following: suppose I have a fifth order polynomial P
> of one variable, to bound over the range [a,b]. I can do this by freshman
> math by calculating the zeros of the derivative (for which there is a closed
> formula; perhaps sophomore math, but nonetheless) Then I throw out those
> most 6 total points consisting of surviving boundary points and a and b to
> get the range. Altogether, the only part of the algorithm that depends on
> [a,b] at all is the exclusion of irrelevant critical points; but while the
> computation of bounds takes longer for big [a,b] because there may be more
> critical points inside, the bounds are exact (to floating point etc etc).
> Isn't this a scaling with the accuracy that is higher than second order?
Of course, for a single variable, we get exact bounds.
For one variables, the global maximum is attained either at the endpoints, ot
at a point where the derivative is equal to 0. So, we get 2 maybe 3 maybe more
points, and looking over all of them, we get the result.
For several variables, a similar result is true for each of n variables
x1,...,xn: for each of the variables, the maximum is attained either at the
left endpoint xi- of the corresponding interval, or at the right endpoint xi+,
or at the point where the partial derivative of the objective function with
respect to xi is equal to 0. For each of n variables, we have 3 possibilities,
so totally, for n variables, we have 3^n possible combinations. Even when we
come up with a simple algorithm to solve each of the 3^n cases, we still have
exponential number of cases.
These calculations are in line with the fact that range estimation is NP-hard
when we consider arbitrary number of variables and is polynomial-time for each
fixed number of variables n (then, this algorithm, in effect, is polynomial,
because 3^n is simply a constant here, althoiugh for large n, it is a
practically huge constant).
Vladik
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 14 18:30:57 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id SAA01265
for reliable_computing-outgoing; Sun, 14 Nov 1999 18:30:57 -0600 (CST)
Received: from mscs.mu.edu (studsys.mscs.mu.edu [134.48.4.15])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id SAA01260
for ; Sun, 14 Nov 1999 18:30:53 -0600 (CST)
Received: (qmail 17832 invoked from network); 15 Nov 1999 00:30:14 -0000
Received: from ppp102.csd.mu.edu (HELO taylor) (134.48.24.2)
by studsys.mscs.mu.edu with SMTP; 15 Nov 1999 00:30:14 -0000
Message-ID: <001001bf2f00$7f9c04e0$02183086@taylor>
From: "George Corliss"
To:
References: <199911142233.PAA07774 [at] cs [dot] utep.edu>
Subject: Re: methods with convergence order higher than two
Date: Sun, 14 Nov 1999 18:29:36 -0600
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Folks,
As this discussion progresses, I am adding it to the
interval FAQ at
www.mscs.mu.edu/~georgec/IFAQ/unnik1.html
George F. Corliss
Dept. Math, Stat, Comp Sci
Marquette University
P.O. Box 1881
Milwaukee, WI 53201-1881 USA
georgec [at] mscs [dot] mu.edu; George.Corliss [at] Marquette [dot] edu
http://www.mscs.mu.edu/~georgec/
Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 14 21:08:50 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id VAA01703
for reliable_computing-outgoing; Sun, 14 Nov 1999 21:08:49 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id VAA01698
for ; Sun, 14 Nov 1999 21:08:47 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id VAA02893;
Sun, 14 Nov 1999 21:08:05 -0600 (CST)
Message-Id: <2.2.32.19991115030930.00742cb4 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sun, 14 Nov 1999 21:09:30 -0600
To: "Martin Berz" , "vladik"
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Cc: ,
"Makino Kyoko (NSCL)"
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Martin,
If I understand the process correctly, then I suspect that the
method will not handle the following problem better than a low-order
extension. (This problem is called
Gritton's second problem, from chemical engineering.) I give the
problem in the form of a Fortran statement for GlobSol. It is an
eighteenth degree polynomial of one variable, and I present it in
Horner's form.
Am I right that a high-order Taylor model will not work better for
this problem? (The function has 18 roots in the interval [-12,8].)
Best regards,
Baker
=====================================================================
! Using Horner's scheme --
F(1) = -0.371936250000000D+03 + X(1)* ( &
-0.791246565600000D+03 + X(1)* ( &
0.404494414300000D+04 + X(1)* ( &
0.978137516700000D+03 + X(1)* ( &
-0.165478928000000D+05 + X(1)* ( &
0.221407282700000D+05 + X(1)* ( &
-0.932654935900000D+04 + X(1)* ( &
-0.351853687200000D+04 + X(1)* ( &
0.478253229600000D+04 + X(1)* ( &
-0.128147944000000D+04 + X(1)* ( &
-0.283443587500000D+03 + X(1)* ( &
0.202627091500000D+03 + X(1)* ( &
-0.161791345900000D+02 + X(1)* ( &
-0.888303902000000D+01 + X(1)* ( &
0.157558017300000D+01 + X(1)* ( &
0.124599084800000D+00 + X(1)* ( &
-0.358914862200000D-01 + X(1)* ( &
-0.195109557600000D-03 + X(1)* ( &
0.227468222900000D-03 ))))))))))))))))))
=====================================================================
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 15 01:53:46 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id BAA02254
for reliable_computing-outgoing; Mon, 15 Nov 1999 01:53:46 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id BAA02249
for ; Mon, 15 Nov 1999 01:53:41 -0600 (CST)
Received: (qmail 10776 invoked from network); 15 Nov 1999 08:15:58 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 15 Nov 1999 08:15:58 -0000
Received: from localhost (nataraj@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id NAA22551;
Mon, 15 Nov 1999 13:21:31 +0530 (IST)
Date: Mon, 15 Nov 1999 13:21:31 +0530 (IST)
From: "Prof. P.S.V. Nataraj"
To: "R. Baker Kearfott"
cc: Martin Berz , vladik ,
reliable_computing [at] interval [dot] usl.edu,
"Makino Kyoko (NSCL)"
Subject: RE: methods with convergence order higher than two
In-Reply-To: <2.2.32.19991115030930.00742cb4 [at] pop [dot] usl.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Colleagues,
As you know, the interpolation forms are given for functions of a single
variable in the book:
"Interval methods for systems of equations" by A. Neumaier, sec2.4,
pages 66-73.
Permit me to quote from the first para of section 2.4 cited above:
"..... In particular, we derive the parabolic boundary value form and
show that it has the cubic approximation property; often it even gives
the range without overestimation".
and to further quote from remark (vi), pg. 72 "The parabolic boundary
value form applies to almost arbitrary functions.... f need not even be
continuous ... ".
Explicit formulae for constructing the parabolic boundary value form are
given in Theorem 2.4.2 of this book.
Moreover, by using the interpolation form determined by k+1 points, one
can obtain convergence of order of k+2.
Also interesting is the remark (vii) on pg. 73 of this book : "... Another
form with cubic approximation order can be constructed using a
Taylor series .... ". The form is then given.
However, all these wonderful and useful results and forms as given by
Prof. Neaumier are specific to functions of a single variable.
Can these results and forms be extended to functions of several variables?
May be it can be done using Taylor series- on the lines given by Neaumier
for the single var. case ?
(Sheela and I are working on the same application problem ).
Thanking you in advance.
Regards,
P.S.V. Nataraj
...........................................................................
Prof. P.S.V. Nataraj Email: nataraj [at] ee [dot] iitb.ernet.in
Systems and Control Engg. Fax: 91-22-5783480; 91-22-5793707
Dept. of Electrical Engg. Ph: 91-22-5782545 extn: 7787 (O) 8887 (R)
IIT, Bombay 400 076 India 91-22-5773757 (Residence)
...........................................................................
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 15 09:46:13 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id JAA03720
for reliable_computing-outgoing; Mon, 15 Nov 1999 09:46:13 -0600 (CST)
Received: from wallace.maths.bath.ac.uk (exim [at] wallace [dot] maths.bath.ac.uk [138.38.100.104])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id JAA03715
for ; Mon, 15 Nov 1999 09:46:10 -0600 (CST)
Received: from [138.38.100.20] (helo=maths.Bath.AC.UK ident=mmdf)
by wallace.maths.bath.ac.uk with smtp (Exim 2.12 #1)
id 11nNGX-0004Do-00
for reliable_computing [at] interval [dot] usl.edu; Mon, 15 Nov 1999 14:37:57 +0000
Received: from localhost by odin.maths.Bath.AC.UK id aa05484;
15 Nov 99 15:45 GMT
Date: Mon, 15 Nov 1999 15:45:53 +0000 (GMT)
From: D S Richardson
To: reliable_computing [at] interval [dot] usl.edu
Subject: MEGA conference
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
I hope this might be of interest to the reliable computing community.
Dan Richardson
\documentstyle{article} \makeatletter
\def\itemize{\ifnum \@itemdepth >3 \@toodeep\else \advance\@itemdepth\@ne
\edef\@itemitem{labelitem\romannumeral\the\@itemdepth}%
\list{\csname\@itemitem\endcsname}{\itemsep=0pt plus 5pt
\def\makelabel##1{\hss\llap{##1}}}\fi} \makeatother
\oddsidemargin -1.2cm \evensidemargin -1.2cm \topmargin -1.5cm
\textwidth 18.3cm \textheight 30cm \thispagestyle{empty} \begin{document}
\begin{center}
\Large\bf
Second Announcement and Call for Papers
\par\vspace{8pt}
\Huge\bf
MEGA 2000
\par\vspace{15pt}
\par\large\bf
The Sixth International Symposium on \par
Effective Methods in Algebraic Geometry
\par\vspace{3pt}
Bath University (United Kingdom), June 20--24, 2000
\par\vspace{20pt}
\par\end{center}
\begin{quote}
MEGA is the acronym for Effective Methods in Algebraic Geometry, a high
standard series of biennial conferences on computational aspects of
Algebraic Geometry. It has taken place in 1990
(Castiglioncello, Italy), 1992 (Nice, France), 1994 (Santander, Spain),1996
(Eindhoven, Nederlands), 1998 (St. Malo, France).
Proceedings of the papers and invited talks presented at the
conference have been published by Birkhauser in the series Progress in
Mathematics (volumes no. 94, 109 and 143) and by the Journal of Pure
and Applied Algebra (volumes no. 117 and 118, and, most recently, in
June 1999, volume 139).
Conference Topics
Effective Methods and Theoretical and Practical Complexity Issues in:
Commutative Algebra, Geometry, Real Geometry, Algebraic Number Theory,
Algebraic Geometry and related fields: Algebraic Analysis of
Differential Equations, Differential Geometry, Associative Algebras,
Group Theory, Algebraic Groups and Lie Algebras, Algebraic and
Differential Topology, as well as applications of these fields
\end{quote}
\begin{center}
\large\bf
Invited Speakers \par
\end{center}
\begin{quote}
Pierette Cassou-Nogues (U. Bordeaux)
Eduardo Cattini (U. Mass at Amherst)
Arjeh Iserles (U. Cambridge)
Janos Kollar (U. Princeton)
Luis Miguel Pardo (U. Cantabria)
John Shackell (U. Kent at Canterbury)
Frank Sottile (U. Wisconsin)
Victor Vassiliev (U. Moscow)
\end{quote}
\begin{center}
\large\bf
Conference Committee \par
\end{center}
\begin{quote}
J.H. Davenport (Bath, Chair),
D. Yu. Grigoriev (Rennes),
Michael Singer (North Carolina State University)
C. Traverso (Pisa)
T. Recio (Santander, Vice Chair)
\end{quote}
\begin{center}
\large\bf
Submissions \par
\end{center}
\par\noindent
%
Papers should be electronically sumitted by January 10, 2000, to the
address: mega2000 [at] posso [dot] dm.unipi.it
Authors who have problems with electronic submissions should contact the
above address.
Submissions should include both a two pages extended abstract and the
full version paper.
In the past, every submission to MEGA has received at least two and usually
three referee reports. We wish to continue this practice and we expect
Extended abstracts to be helpful speeding up finding referee reports.
Full papers will be refereed from January to March 2000 and the final
decision by the Executive Committee will be communicated to the authors by
mid-April, 2000.
\begin{itemize}
\item
{\bf English} is the only official language of the Symposium.
\item
Submission of essentially the same paper elsewhere is not allowed.
\item
Submissions will be refereed both for presentation at the Symposium
and for inclusion in the Proceedings (to be published after the Symposium).
%
\end{itemize}
\vspace{10pt}
\begin{quote}
James Davenport, Daniel Richardson, Nicolai Vorobjov \\
Department of Mathematical Sciences \\
Bath University \\
Bath BA2 7AY \\
U.K. \\
E--mail: {\tt mega2000 [at] maths [dot] bath.ac.uk} \\
For more information, see : {\tt http://www.maths.bath.ac.uk/CONFERENCES/mega2000/}
\end{quote}
\end{document}
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 15 10:00:13 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA03976
for reliable_computing-outgoing; Mon, 15 Nov 1999 10:00:13 -0600 (CST)
Received: from suntana.fh-konstanz.de (suntana.fh-konstanz.de [141.37.9.230])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA03971
for ; Mon, 15 Nov 1999 10:00:09 -0600 (CST)
Received: from fh-konstanz.de (dialup160.fh-konstanz.de [141.37.217.160])
by suntana.fh-konstanz.de (8.9.3/8.9.3) with ESMTP id RAA14784
for ; Mon, 15 Nov 1999 17:00:05 +0100 (MET)
Message-ID: <383030EF.6472D52A@fh-konstanz.de>
Date: Mon, 15 Nov 1999 17:12:31 +0100
From: Garloff [at] suntana [dot] fh-konstanz.de,
=?iso-8859-1?Q?J=FCrgen?=
X-Mailer: Mozilla 4.51 [en] (Win98; I)
X-Accept-Language: en
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] usl.edu
Subject: ER:methods with convergence order higher than two
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Colleagues,
in the discussion the question of determining the range of a polynomial
over a box came up. I would like to remind that an approach proven to be
very useful for this task is the expansion of the given polynomial into
Bernstein polynomials, the so-called Bernstein form; for the univariate
case see, e.g.,
H.C.Fisher, 'Range computations and applications', in 'Contributions to
Computer Arithmetic and Self-Validating Numerical Methods', C.Ullrich,
Ed., Amsterdam, J.C.Baltzer, 1990, pp.197-211
and for the multivariate case
J.Garloff, 'The Bernstein algorithm', Interval Computations vol.2, 1993,
pp.154-168.
A nearly exhaustive bibliography can be found in
R.Hungerbuehler and J.Garloff, Reliable Computing, vol.4, 1998, pp.3-13.
Special feartures of the approach are:.
1. It can be decided whether the bounds obtained by this approach are
sharp.
2. For suffieciently small boxes the Bernstein form gives the exact
range. This was proven by V.Stahl in his dissertation at RISC/Linz for
the univariate case, but the proof caries over to the multivariate case.
3. When bisecting a box and applying the Bernstein form to one of the
two subboxes to get an enclosure for the range over this subbox one
obtains without any extra cost an enclosure for the range over the other
box.
Regards,
Juergen Garloff
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 15 10:28:15 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA04413
for reliable_computing-outgoing; Mon, 15 Nov 1999 10:28:15 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA04408
for ; Mon, 15 Nov 1999 10:27:56 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id JAA11138;
Mon, 15 Nov 1999 09:26:09 -0700 (MST)
Message-Id: <199911151626.JAA11138 [at] cs [dot] utep.edu>
Date: Mon, 15 Nov 1999 09:26:09 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: RE: methods with convergence order higher than two
To: nataraj [at] ee [dot] iitb.ernet.in, rbk [at] usl [dot] edu, neum [at] cma [dot] univie.ac.at
Cc: berz [at] msu [dot] edu, makino [at] nscl [dot] msu.edu, vladik [at] cs [dot] utep.edu,
reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: ggN0cnJrsZLnceEjRxzXiA==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Arnold, Thanks a lot for your thoughtful comments. May I make one minor
comment.
> Date: Mon, 15 Nov 1999 10:45:55 +0100 (MET)
> From: Arnold Neumaier
> To: nataraj [at] ee [dot] iitb.ernet.in, rbk [at] usl [dot] edu
> Subject: RE: methods with convergence order higher than two
> Cc: berz [at] msu [dot] edu, makino [at] nscl [dot] msu.edu, neum [at] cma [dot] univie.ac.at,
vladik [at] cs [dot] utep.edu
>
> P.S.V. Nataraj wrote,
>
> >> interpolation forms are given for functions of a single
> variable in the book:
> "Interval methods for systems of equations" by A. Neumaier, sec2.4,
> pages 66-73. [...] However, all these wonderful and useful results
> and forms [...] are specific to functions of a single variable.
> Can these results and forms be extended to functions of several
> variables?<<
>
> In principle, it seems possible to generalize these univariate
> results to higher dimension, in the sense that one can probably
> find analogues that replace the enclosure problem for a general function
> f(x) by that of a suitable interval quadratic function [q(x)] such
> that the overestimation of the range of f(x) by that of [q(x)] is
> of order O(rad(x)^3). And it is probably valuable to explore the
> various possibilities to do this. However, this only reduces the
> general problem to that of finding the range of a multivariate
> quadratic, and there is no polynomial way to do that in general
> (unless P=NP). On the other hand, asking for an asymptotic result
> is an easier problem, since it means that one only wants O(eps^3)
> accuracy and only for boxes with radius O(eps), and midpoint and
> coefficients essentially independent of eps. It seems that the
> known complexity results don't cover this case,
It depends, of course, on how we interpret this statement precisely, but as I
interpret it, known complexity results do cover this case as well. Namely,
Theorem 3.2 from our book proves, in effect, that for every delta>0 and
epsilon>0, the problem of computing the range of a quadratic polynomial on
intervals of width delta with accuracy epsilon is NP-hard. This is true, in
particular, if we take epsilon=delta^3 or whetever.
The proof (this is actually one of the results by Patrick Kahl, one of the
book's co-authors who wrote his these on extending known NP-hardness results to
narrow input intervals) is rather straighforward: we know that computing a
range of a quadratic polynomial is NP-hard. In this proof, we consider
quadratic polynomials f(x1,...,xn) with coefficients which take integer values
from -3 to 3 and with the range of every variable xi the interval [0,1] (we can
take [1,2] if we want, then the coefficients of the polynomial will slightly
increase). To prove that the problem is NP-hard for narrow intervals, we can
consider a new polynomial F(y1,...,yn)=f(x1/delta,...,xn/delta) (or with some
similar linear functions). For this new polynomial, the range computation
problem is NP-hard for ranges of yi of width delta (they correspond to ranges
of xi of width 1).
The coefficients of the new polynomial are of order 1/delta^2$, so we can
condisder a new polynomial delta^2F(y1,..,yn); for new polynomial, the
coefficients are uniformly bounded, but computing its range with accuracy
epslion\times delta^2 is NP-hard. So, it is NP-hard to even compute the range
with quadratic accuracy ~ delta^2. (Therefore, for a more complex problem of
computing the range with the accuracy delta^3 it is also NP-hard).
On the other hand, there may be other possible formulations of this problem
which may turn out to be polynomial-time; Arnold, if you have any intuition on
what these formulations may be, please let us know.
> and if this is the
> case there is still some work left to be done, and perhaps a positive
> (polynomial) answer is possible for the quadratic case. Then it would
> be likely to extend it to the general case, too, by looking more
> closely at what happens to the eps'es.
>
> In any case, the problem of finding good O(n^3) bounds for the
> range of a multivariate quadratic is a very important one, and even if
> one cannot get the exact range it would be very useful to know what
> one c a n get with a reasonable amount of work, and whether the
> class of problems where the exponential effort is required is small
> or large.
>
> And finding the best ways of reducing a nonlinear problem to one that
> is quadratic is also a useful enterprise.
>
> I think in both areas the last word hasn't been said yet, and I'd like
> to encourage the interval community to investigate these topics more
> closely, both by means of algorithmic advances, comparative numerical
> studies, and theoretical analysis of the potential and the limits of
> various approaches.
>
> Arnold Neumaier
>
From owner-reliable_computing [at] interval [dot] usl.edu Tue Nov 16 17:45:56 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id RAA06924
for reliable_computing-outgoing; Tue, 16 Nov 1999 17:45:56 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id RAA06919
for ; Tue, 16 Nov 1999 17:45:48 -0600 (CST)
Received: (qmail 26380 invoked from network); 17 Nov 1999 00:08:06 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 17 Nov 1999 00:08:06 -0000
Received: from localhost (jjbarve@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id FAA14220;
Wed, 17 Nov 1999 05:13:35 +0530 (IST)
Date: Wed, 17 Nov 1999 05:13:35 +0530 (IST)
From: "Barve Jayesh J., Res. Schol., SYSCON"
To: interval computing
cc: Sheela [at] bhairav [dot] ee.iitb.ernet.in,
"Prof. P.S.V. Nataraj"
Subject: .. Sheela's que...
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Colleagues,
1) I and Ms.Sheela, both are working under Prof.P.S.V.Nataraj
doing research in applications of interval arithmetic.
2) I also have been reading the discussions on the reliable_computing
list initiated by Sheela. Just now I was going through Martin Berz's
papers and trying something. I am tempted to do the following remarks
based on my observations.
Though the following remarks are not straight away related to
convergence order of higher order etc.
But they are related to it based on the actual motivation of
using higher order convergence forms etc. to increase computational
efficiency and reduce over-estimation for range computation.
3) It is very useful to do monotonicity check for the function
f(X) over the given interval vector X=[X1 X2 .. Xn]. It may be
monotonic along each or some variables X1,X2.. in the given domain
or in part of the domain. (Though this is well-known, it might
be over-looked many times to do monotonicity check.)
Observation:
In fact for the 3-dimensional complicated function on page 6 of the
following reference, the exact range is possible to compute just by
evaluating the function at 8 corner points of the 3-D box of input
interval [x1 x2 x3]. Because it is monotonic along each variable
x1, x2 and x3.
(Ref: K. Makino and Martin Berz ," Efficient Control of the dependency
Problem based on Taylor Model Methods', Reliable Computing 5, 3-12,
1999 )
It is found by gradient evaluation that the function is monotonic along
each variable. (I computed gradients using 'gradientinit' tool of
INTVAL toolbox for MATLAB of Rump etal).
The gradients of f(x1,x2,x3) are found to be ---
intval gradient derivative(s) yg.dx =
Column 1
[ -4.890465660975971e-001, -2.093516938447799e-001]
Column 2
[ 9.255280249313442e+000, 2.113569763264646e+001]
Column 3
[ -4.569281010721819e+001, -7.059391352010891e+000]
It clearly shows monoticity of function along each variable, for
the given input intervals x1,x2 and x3.
4) Though this may not happen for each function, the monotonicity check
of the function f(X) for the given interval X (or may be parts of X)
may obviously lead to more accurate and efficient computation of range.
5) I apologies, if I am wrong some where in my remarks, being a new user
of interval arithmetic. And wel-come corrections, if any.
With regards
**************************************************************************
| J.J.Barve | also-- |
| Research Scholar (Systems & Control) | Asst. Prof.-Instru. & Control |
| Hostel-1, Room No. 243 | D.D.Institute of Tech. |
| Indian Institute of Technology, Powai | NADIAD- 387 001 |
| Mumbai- 400 076 (INDIA) | Gujarat, INDIA |
| Ph: 0091-022-769 2545-7887 | Ph: 0091-0268-61406 |
| E-mail: jjbarve [at] ee [dot] iitb.ernet.in | E-mail: barve [at] ddit [dot] ernet.in |
**************************************************************************
From owner-reliable_computing [at] interval [dot] usl.edu Tue Nov 16 23:12:57 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id XAA07725
for reliable_computing-outgoing; Tue, 16 Nov 1999 23:12:56 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id XAA07720
for ; Tue, 16 Nov 1999 23:12:32 -0600 (CST)
Received: (qmail 30389 invoked from network); 17 Nov 1999 05:34:28 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 17 Nov 1999 05:34:28 -0000
Received: from localhost (nataraj@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id KAA21995;
Wed, 17 Nov 1999 10:39:55 +0530 (IST)
Date: Wed, 17 Nov 1999 10:39:55 +0530 (IST)
From: "Prof. P.S.V. Nataraj"
To: Garloff [at] suntana [dot] fh-konstanz.de,
=?iso-8859-1?Q?J=FCrgen?=
cc: reliable_computing [at] interval [dot] usl.edu
Subject: Re: ER:methods with convergence order higher than two
In-Reply-To: <383030EF.6472D52A@fh-konstanz.de>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Dr. Garloff,
Thank you for the info on Bernstein forms.
The application Sheela and I are working on involves:
(a) functions of several variables
(typically 3-5, sometimes even 7-8 variables).
(b) The terms could involve any of the built-in functions of a
programming language, such as FORTRAN.
(c) The functions be as arbitrary as possible
- to the extent that their interval extensions exist in the domain
intervals.
Please tell whether the Bernstein form are useful in this case?
and what assumptions on the functions would have to be made ?
Regards,
P.S.V. Nataraj
...........................................................................
Prof. P.S.V. Nataraj Email: nataraj [at] ee [dot] iitb.ernet.in
Systems and Control Engg. Fax: 91-22-5783480; 91-22-5793707
Dept. of Electrical Engg. Ph: 91-22-5782545 extn: 7787 (O) 8887 (R)
IIT, Bombay 400 076 India 91-22-5773757 (Residence)
...........................................................................
On Mon, 15 Nov 1999 Garloff [at] suntana [dot] fh-konstanz.de wrote:
> Dear Colleagues,
> in the discussion the question of determining the range of a polynomial
> over a box came up. I would like to remind that an approach proven to be
> very useful for this task is the expansion of the given polynomial into
> Bernstein polynomials, the so-called Bernstein form; for the univariate
> case see, e.g.,
>
> H.C.Fisher, 'Range computations and applications', in 'Contributions to
> Computer Arithmetic and Self-Validating Numerical Methods', C.Ullrich,
> Ed., Amsterdam, J.C.Baltzer, 1990, pp.197-211
>
> and for the multivariate case
> J.Garloff, 'The Bernstein algorithm', Interval Computations vol.2, 1993,
> pp.154-168.
>
> A nearly exhaustive bibliography can be found in
> R.Hungerbuehler and J.Garloff, Reliable Computing, vol.4, 1998, pp.3-13.
>
> Special feartures of the approach are:.
> 1. It can be decided whether the bounds obtained by this approach are
> sharp.
> 2. For suffieciently small boxes the Bernstein form gives the exact
> range. This was proven by V.Stahl in his dissertation at RISC/Linz for
> the univariate case, but the proof caries over to the multivariate case.
>
> 3. When bisecting a box and applying the Bernstein form to one of the
> two subboxes to get an enclosure for the range over this subbox one
> obtains without any extra cost an enclosure for the range over the other
> box.
>
> Regards,
> Juergen Garloff
>
>
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 00:06:39 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id AAA08113
for reliable_computing-outgoing; Wed, 17 Nov 1999 00:06:39 -0600 (CST)
Received: from mailhost.iitb.ac.in (mailhost.iitb.ac.in [202.54.44.115])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id AAA08108
for ; Wed, 17 Nov 1999 00:06:25 -0600 (CST)
Received: (qmail 32114 invoked from network); 17 Nov 1999 06:28:32 -0000
Received: from bhairav.ee.iitb.ernet.in (144.16.100.100)
by mailhost.iitb.ac.in with SMTP; 17 Nov 1999 06:28:32 -0000
Received: from localhost (nataraj@localhost)
by bhairav.ee.iitb.ernet.in (8.8.8/8.8.8) with SMTP id LAA24209;
Wed, 17 Nov 1999 11:33:31 +0530 (IST)
Date: Wed, 17 Nov 1999 11:33:31 +0530 (IST)
From: "Prof. P.S.V. Nataraj"
To: Martin Berz
cc: vladik , rbk [at] usl [dot] edu,
reliable_computing [at] interval [dot] usl.edu,
"Makino Kyoko (NSCL)"
Subject: RE: methods with convergence order higher than two
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Dr. Berz,
I have made a first reading of your papers on the Taylor model computation
for multivariate functions.
The Taylor model method appears to be quite promising in engineering
applications such as ours, where there are several (upto 7-8) variables
and functions can involve any of the built-in functions of FORTRAN.
As I understand from your papers, the Taylor model computation can be
done automatically even for high orders and a moderately large number
of variables (both upto 10) using software available at your university.
However, to be of general use in practical problems having thicker domain
intervals (the examples in your papers have fairly thin domain
intervals), it is necessary to combine the Taylor models with other
schemes (at least, with sub-division) for range computation with higher
order ( > 2) convergence.
Please tell if your univ's software for automatic Taylor model computation
does support user defined routines having interval arithmetic
operations?
The idea is to be able to combine the Taylor model with
sub-division, or use it along with more sophisticated interval
global optimization techniques for efficient range computation over large
boxes.
Thanking you in advance,
Regards,
P.S.V. Nataraj
...........................................................................
Prof. P.S.V. Nataraj Email: nataraj [at] ee [dot] iitb.ernet.in
Systems and Control Engg. Fax: 91-22-5783480; 91-22-5793707
Dept. of Electrical Engg. Ph: 91-22-5782545 extn: 7787 (O) 8887 (R)
IIT, Bombay 400 076 India 91-22-5773757 (Residence)
...........................................................................
On Sun, 14 Nov 1999, Martin Berz wrote:
> Baker, Vladik, Sheela,
>
> now I had taken off Saturday, and found out that I apparently missed
> something interesting - sorry for keeping people waiting, let me try to
> address some of the points now. Actually this is a good example of the nice
> job that Interval people, and in particular Baker and Vladik, are doing
> about getting to the bottom of may interval-related topics in this useful
> discussion server.
>
> By the time I am now re-entering the discussion, quite a few aspects have
> been touched upon, and I am basing my answer mostly on Vladik's last email
> because it attempts to summarize many of the points and hence allows me to
> insert my answers in perhaps a most structured way. In addition, I will try
> to interweave other questions that seem to have come up by Baker and Sheela;
> if I may have missed something, please ask again. Please note, however, that
> because of a commitment this Sunday afternoon, I may not be able to reply
> before Monday ( perhaps I have to re-think the amount of dedication to my
> work ;-)... ) To close the introduction, Vladik, can you send me a paper or
> .ps copy of your IEEE complexity paper?
>
> Martin
>
> > -----Original Message-----
> > From: owner-reliable_computing [at] interval [dot] usl.edu
> > [mailto:owner-reliable_computing [at] interval [dot] usl.edu]On Behalf Of vladik
> > Sent: Saturday, November 13, 1999 4:25 PM
> > To: vladik [at] cs [dot] utep.edu; rbk [at] usl [dot] edu
> > Cc: reliable_computing [at] interval [dot] usl.edu
> > Subject: RE: methods with convergence order higher than two
> >
> >
> > Dear Baker,
> >
> > I think that this discussion is very useful because it attracts the
> > participants' attention to Martin's very important algorithms.
> > Thanks for the
> > references. I have read the papers again, and now I understand
> > hopefully the
> > situation better.
> >
> > I want to present my understanding in the form that Martin and I
> > are both right
> > (actually, Martin is more right that I am, because
> > * I am right formally, while
> > * he is right in reality).
> > Here is my explanation.
> >
> > As I understand it, Martin's idea of computing the range as
> > described in his
> > paper with Makino (Vol. 5 of Relibale Computing) is as follows:
> > * Let us assume that we have a function f(x1,...,xn) which may
> > include trigonometric and other special functions.
> > * If we use naive interval computations to estimate the range
> > of this function on a small box, we may get a big overestimation.
> > * Instead of applying naive interval computations (or centered method,
> > or any other known technique), we
> > * first apply Taylor method and
> > find the Taylor expansion of the given function in the vicinity
> > of the given point (the center of the small box on which we want
> > to estimate the range), i.e., a polynomial P(x1,...,xn) together
> > with the interval which estimates the remainder.
>
> This is correct. To clarify, we are using floating-point Taylor
> coefficients; and furthermore it is very important to calculate the
> remainder bound in parallel with the multivariate Taylor polynomial. One
> could, in principle, also use high-order AD to shove the domain through the
> respective (n+1)st order derivatives, but this actually leads to much more
> pessimistic results because of cancellation etc etc.
>
> >
> > The difference
> > between f and P can be made as small as possible: we can have
> > 3rd, 4th, 12th order etc. methods depending on how many terms we
> > preserve in the Taylor expansion
>
> True, down to some reasonable multiple of the "accuracy floor" of your
> floating point environment. The method will stabilize there, since
> eventually floating point errors in the Taylor coefficient calculation
> (which are lumped into the remainder bound) will take over and start
> dominating things.
>
> > * Then, we apply naive interval computations or any other known
> > techniques (centered, etc.) to estimate the range of the polynomial
>
> Yes, we estimate the range of the polynomial, and we COULD do that with
> naive intervals, centered form etc, or an off-the-shelf general range
> bounder like Baker's. However, because of the basic algorithm, the
> polynomials that occur have very special structure: their contribution
> decreases rapidly with order. For if this is not the case, the high-order
> Taylor approximation doesn't produce a sharp remainder - it's like being
> outside the range of convergence of Newton's method, to use a second order
> analogy. This is the key point why the polynomial can be done efficiently,
> and also why we are as far as I can see not in the terrain where the normal
> complexity statements have bearing. I will provide more detail below
> connected to the more concise question from Baker, and keep going for now in
> order to not interrupt the flow of Vladik's summary too much.
>
> > * After that, add the interval for the remainder to get the final
> > enclosure.
> >
>
> True. And clarifying Baker's comment, it is indeed bounding over boxes, not
> point evaluations, that we are considering here. Also, it doesn't rest on
> special assumptions on the transfer function (in fact, the earlier work from
> 1994 that Baker quotes did do that in an interesting way - but let me not
> get into details about that here). Finally, Sheela, the functions you
> describe are in the class we studying with the methods.
>
> > On the estimate-polynomial's-range step, we get an NP-hard
> > problem for which it
> > is impossible to have an estimate which is always of 3rd order
> > (see our paper
> > with Slava). As a result, the total order of the two-step
> > procedure cannot be
> > 3rd order, so formally speaking, my answer is right that there is
> > no 3rd order
> > procedure which can help.
> >
> > In particular, when we start with a quadratic polynomial in the
> > first place
> > (and this problem is NP-hard for quadratic polynomials already), Taylor's
> > approximation is exact, so there is no remainder at all (the
> > approximation of f
> > by P is accuracy with 3rd, 4th, etc., any degree). However, in
> > this particular
> > case, Martin's method does not give us any new estimate for the range: it
> > simply says that we have to use the estimate for the original polynomial.
>
> Yes in the sense that there is no remainder bound, and we are faced with the
> task of bounding the polynomial just as before. But besides, the algorithms
> detects whether the polynomial is favorable for the method to work (i.e.
> with sufficiently rapidly decreasing high-order contributions), or whether
> we may have to narrow the original domain box. As a consequence, our
> polynomial bounder gets invoked only in the favorable case.
>
> >
> > For most small sub-boxes of the original box, the function P will
> > be monotonic
> > in all the variables, so we can get the exact estimate. In a few
> > points where
> > the derivatives are close to 0 we may have an overestimation, and this
> > overestimation may be of 2nd order. This explains in what sense I
> > am right.
> >
>
> I think Vladik's thoughts go essentially in the right direction; while the
> function doesn't have to be monotonic, the criterion is that it must be of
> the form that the orders in the Taylor expansion converge quickly enough. In
> algorithmic practice, this aspect is actually checked at many places as we
> go through the code. And whenever doing Taylor models, you may want to
> carry along a naive interval estimator in parallel as well; if one has such
> large domains where high-order Taylor doesn't work anymore (and because of
> the high-order behavior, Taylor may actually be worse than naive
> intervals), then the algorithm falls back to lower order Taylor, or even
> regular intervals.
>
> This is actually rather similar in flavor to a step size controller in a
> numeric integrator, where often essentially two algorithms of different
> order are run against each other, and the difference is used as a measure of
> accuracy; which merely means that the high orders fall of fast enough. Using
> this diagnostic, one doesn't loose time for needless Taylor calculations
> (except for the first diagnostis of "trouble"), and is guaranteed to always
> do at least as well as naive interval. But in addition one has a reasonable
> estimate of how good (or rather, bad) the interval result is to be expected
> to be, which can be used in the branch-and-bound controller. In practice, of
> course once you reach a certain threshold, Taylor has a tendency to take
> over very beneficially.
>
> > On the other hand, Martin was absolutely right because he
> > understood Sheela's
> > question not as
> > * a formal question on whether 3rd and 4th order metjods are
> > possible, but as
> > * a practical question on how to best estimate the range.
> > The function that Sheela has in mind is exactly the type to which
> > Martin's
> > method is applied. In this case, if
> > * instead of applying interval computation techniques to the original
> > expression,
> > * we first replace it with its Taylor series,
> > we will most probably get a much better estimate
>
> basically yes.
>
> (although if we
> > take the error
> > of estimating the range of the polynomial P into consideration,
> > this estimate
> > will not be necessarily of 3rd or 4th order).
>
> Now let us see about the polynomial bounding. As alluded above, it rests on
> the fact of sufficiently rapid decrease with order; as such, it is not
> applicable to the general polynomial bounding problem (unless of course you
> first allow to split the boxes over which these are needed so they become
> sufficently small, the diagnostic of which with centered form etc goes
> quadratic - so no problem with the complexity theory here). The question
> about dedicated polynomial bounders in general was actually posed a few
> months ago on this discussion board, but I didn't provide a remark because
> our case is of course special. From Vladik's complexity point of view, it
> would be somewhat interesting whether
>
> 1) this essential phenomenon of "rapidly decreasing order" can be described
> somewhat rigorously within the framework of complexity, and if this is the
> case,
>
> 2) whether there are any known scaling laws for this particular case.
>
> Be this as it may, here is how our algorithm for polynomials with rapidly
> decreasing order works:
>
> 1) First, split the polynomial into a (low-order) part L for which we can
> determine location of points that provide maxima exactly, and the high-order
> rest H for which we cannot. For example, if L ist just the linear part, it
> can be bounded exactly, and the maximum always occurs in one of the corners
> in the multidimensional box, and it's even very cheap, with essentially no
> penalty for higher orders. Second order L (with fixed variable numbers - see
> Vladik's comment on complexity as function of number of variables) can be
> done reasonably easily for any number of variables; to this end, consider
> the edges, which gives second order of one degree less (and then iterate),
> and look on the inside which gives a linear system via vanishing gradient.
> To higher orders of L, I will come back below, in the framework of
> complexity discussions.
>
> 2) Next determine a crude bound B(H) for H over the entire box (e.g. by
> naive intervals etc; in fact, in our Taylor model arithmetic, we obtain
> these sharper than with regular intervals as a free by-product).
>
> 3) Looking at the exact maximizing points of L and the crude higher order
> bound B(H), and the fact that the L dominates the behavior since by
> definition high orders are assumed to decrease quickly, one can shrink the
> box over which the maximum occurs. For L linear, the size is determined by
> something like B(H) / B(grad L), and we have quadratic convergence. For L
> second order it's cubic, etc.
>
> In practice, this polynomial bound works nicely, and compared to the large
> amount of floating point arithmetic going into the Taylor coefficient
> calculations (which we note doesn't have to be iterated), the polynomial
> bounding doesn't contribute so significantly to the effort. So for practical
> purposes, performance is usually dominated by the desired order of the
> Taylor model, not the polynomial bounder.
>
> >
> > Summarizing:
> > * Martin is more right: from the practical viewpoint, by using his method,
> > we get a better estimate for the range, and the first part of the error
> > (approximating f by a polynomial P) can be made 3rd order, 4th
> > order etc.
>
> >
> > * I am also right (theoretically) because although Martin's method will
> > probably lead to a good estimate, we will not necessarily get the
> > estimate of a range which is of 3rd order in terms of the widths of the
> > original intervals, because the second part of his algorithm
> > (estimating the range of the polynomial) may lead to larger errors.
> >
>
> I believe that is true if we consider all possible scenarios for ranges;
> currenly of course the accuracy requirement for the polynomial bounder is
> controlled by the accuracy of the remainder bound (there is no point getting
> the polynomial bounded say more than 10 times sharper than the remainder
> bound), which throws a somewhat ugly termination criterion in the
> theoretical study of algorithmic performance. Nevertheless, while for a many
> typically occuring ranges it works very nicely, it may break down
> asymptotically. Two scenarios:
>
> 1) For too large domains outside the range of "orders decreasing quickly",
> the Taylor remainder bound becomes extremely pessimistic, and you loose with
> order (n+1) ... No need for sharp polynomial bounding anymore, but you are
> dead nonetheless.
>
> 2) For extremely small domains, assuming an "accuracy floor" substantially
> below what we typically have for floating point, we may get so extremely
> tiny remainder bounds scaling with order (n+1) that the polynomial bounder
> has a very hard time to reach a similar sharpness.
>
> > So:
> > * theoretically, unless there is an error in our paper, I believe we
> > are right literally, in the sense that no 3rd order method of
> > estimating the range of the function is possible;
>
> Vladik, let me ask the following: suppose I have a fifth order polynomial P
> of one variable, to bound over the range [a,b]. I can do this by freshman
> math by calculating the zeros of the derivative (for which there is a closed
> formula; perhaps sophomore math, but nonetheless) Then I throw out those
> critical points that lie outside [a,b] and evaluate the function at the at
> most 6 total points consisting of surviving boundary points and a and b to
> get the range. Altogether, the only part of the algorithm that depends on
> [a,b] at all is the exclusion of irrelevant critical points; but while the
> computation of bounds takes longer for big [a,b] because there may be more
> critical points inside, the bounds are exact (to floating point etc etc).
> Isn't this a scaling with the accuracy that is higher than second order?
>
> While of course this fifth order polynomial is highly hypothetical for the
> general function case, it does appear in the fifth order one variable Taylor
> model problem.
>
> > * in practice, however, Maryin is right, because a very good
> > approximation method is possible, and in some sense (namely,
> > if we only consider the error of the first step) it is of 3rd order.
> >
> > If, as I understand it, Sheela really wants to compute the range
> > nicely, then
> > we should accept the fact that it is theoretically impossible to
> > get a range
> > which is 3rd order estimate and use the best possible known
> > algorithm (Martin's
> > may as well be a one) for which at least the first component of
> > the error is
> > 3rd order.
> >
> > Vladik
> >
> >
>
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 02:56:55 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id CAA08562
for reliable_computing-outgoing; Wed, 17 Nov 1999 02:56:55 -0600 (CST)
Received: from yonge.cs.toronto.edu (root [at] yonge [dot] cs.toronto.edu [128.100.2.11])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id CAA08557
for ; Wed, 17 Nov 1999 02:56:52 -0600 (CST)
Received: from jane.cs.toronto.edu ([128.100.2.31]) by yonge.cs.toronto.edu with SMTP id <86549-21932>; Wed, 17 Nov 1999 03:56:41 -0500
Received: from dvp.cs.toronto.edu by jane.cs.toronto.edu id <96311-4904>; Wed, 17 Nov 1999 03:56:36 -0500
From: Jeff Tupper
To: reliable_computing [at] interval [dot] usl.edu
Subject: Generalized Interval Methods
Message-Id: <99Nov17.035636edt.96311-4904 [at] jane [dot] cs.toronto.edu>
Date: Wed, 17 Nov 1999 03:56:27 -0500
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
With all of the discussion about generalized interval methods, I thought I
would throw in my comments:
- There may be a number of "Taylor Model" packages around. I developed
such a package while working on my M.Sc. thesis for nth degree polynomials
in two variables. (I put "Taylor Model" in quotation since I wasn't aware
of Berz's work until this thread started.)
- I later decided to instead use a separate function for the upper and lower
bounds rather than a single function plus an interval uncertainty since I
thought that such an approach was mathematically more elegant (bounding
functions with functions).
Some of the practical reasons for my choice:
- Using two distinct functions allows for better bounds, especially when
the resulting interval is unbounded below or above as happens when
dividing by an interval that contains zero.
Caution: Better bounds may well come at the expense of using more basic
operations to implement interval operations. With two distinct functions,
more information must be kept in memory for each interval.
- I was interested in evaluating simple functions (shallow evaluation depth)
over large ranges and not with iterated evaluations (deep evaluation depth)
over small ranges.
- Implementing functions such as the floor function is a little paradigm-
challenging with a Taylor Model since one must decide whether x is
a reasonable approximation to the derivative (which is zero) when
evaluating over large domains. (Approximating the derivative with the
functional bound is a useful heuristic which works well asymptotically,
but better choices exist and may be appropriate for evaluations over large
domains.)
- Since my package only tracks the side of the interval that matters, excess
resource usage due to two distinct functions is mitigated. For example,
after an evaluation of a function over a region is performed and it is
determined that only the upper bound is needed, future evaluations over
sub-regions will only calculate the upper bound - this is done over the
evaluation tree independently for each operation. Often, with my
application, only an upper or lower bound is desired on the final range
of a function.
Other comments:
- Affine arithmetic can also provide sharper bounds than standard interval
arithmetic. I decided against automatically introducing new variables
since I wanted a direct correspondence between high-level (application)
variables and low-level (interval package) variables and thought it would
not be a wise use of computer resources to track all relationships. (From
what I have read from more recent AA papers, AA users are now collapsing /
combining some low-level variables while the application executes.) (Also,
I occasionally introduce new variables when it is quite likely to help
significantly.)
- I do think keeping track of bounds on other properties of function
evaluations (in addition to the range) is a good general method -
continuity and domain of definition as done in my M.Sc. thesis for
example. Recently, I've been working on tracking other properties
(continuity of closure is useful when evaluating exponentiation with
interval bases containing negative values).
- I would appreciate a reference to the first work on Taylor Models.
- There is a general trade-off between quality of generated bounds and
the amount of computer resources used to generate them. For example,
are there any results which establish the minimum amount of basic
operations needed for each interval operation to get quadratically
converging bounds? (This would depend on the form of the function
used for the bounds, of course.)
- For those wondering what is happening with GrafEq, the graphing package
that is the "physical embodiment" of some of the ideas of my M.Sc.
thesis: it is currently being translated into other languages. It is
available in English and Dutch currently. Danish, Korean, Chinese, German,
and French are currently being worked on. If anyone is interested in
helping with translations into other languages, I am sure peda [at] peda [dot] com
would be interested. Free licenses for interval researchers are still
available (contact me) - the program is downloadable from
http://www.peda.com/grafeq (It is a good example of interval methods
since it is faster than standard graphers in many cases and produces
better results. I'm still not aware of any other grapher that proves pixels
correct. A number of interval graphers have come since my M.Sc. thesis
but the ones I have seen all do subtractive graphing only - they prove
the absence of solutions but not the presence of solutions.)
Jeff
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 10:14:45 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA09236
for reliable_computing-outgoing; Wed, 17 Nov 1999 10:14:45 -0600 (CST)
Received: from pilot021.cl.msu.edu (pilot021.cl.msu.edu [35.9.5.121])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA09231
for ; Wed, 17 Nov 1999 10:14:23 -0600 (CST)
Received: from berz (berz.user.msu.edu [35.10.52.114])
by pilot021.cl.msu.edu (8.9.1a/8.9.1) with SMTP id LAA57186;
Wed, 17 Nov 1999 11:13:18 -0500
From: "Martin Berz"
To: "Barve Jayesh J., Res. Schol., SYSCON" ,
"interval computing"
Cc: ,
"Prof. P.S.V. Nataraj"
Subject: RE: .. Sheela's que...
Date: Wed, 17 Nov 1999 11:13:09 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
In-Reply-To:
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Mr. Barve,
> 2) I also have been reading the discussions on the reliable_computing
> list initiated by Sheela. Just now I was going through Martin Berz's
> papers and trying something. I am tempted to do the following remarks
> based on my observations.
> Though the following remarks are not straight away related to
> convergence order of higher order etc.
> But they are related to it based on the actual motivation of
> using higher order convergence forms etc. to increase computational
> efficiency and reduce over-estimation for range computation.
>
>
> 3) It is very useful to do monotonicity check for the function
> f(X) over the given interval vector X=[X1 X2 .. Xn]. It may be
> monotonic along each or some variables X1,X2.. in the given domain
> or in part of the domain. (Though this is well-known, it might
> be over-looked many times to do monotonicity check.)
>
In principle such checks may be useful in some cases and make the
computation of the bound very easy if they apply. In the beginning we have
in fact thought about including this check in the procedure. However, one
would still need to find range bounds for the derivatives, and if they do
contain zero, not much is gained. In general, the range bounding of the
derivatives is the same type of problem that we originally set out except
one order lower. Perhaps it can be done with lower accuracy; but if it
doesn't allow the exclusion of zero very quickly (say by mere interval
evaluation), then it's tough to decide how far to continue this thread if
the end result may be that anyway we don't have monotonicity.
The algorithm for the polynomial bounding we are currently using in fact has
most of the effect that you may want to achieve with the monotonicity test
built in; as illustrated in the description of the algorithm that we
circulated a few days ago, we use the slope of the linear part of the
polynomial (which is of course boundable exactly and easily) and the fact
that the higher orders converge to make an estimate of sub-regions where the
maxima have to occur, and iterate a few times.
> Observation:
>
> In fact for the 3-dimensional complicated function on page 6 of the
> following reference, the exact range is possible to compute just by
> evaluating the function at 8 corner points of the 3-D box of input
> interval [x1 x2 x3]. Because it is monotonic along each variable
> x1, x2 and x3.
>
> (Ref: K. Makino and Martin Berz ," Efficient Control of the dependency
> Problem based on Taylor Model Methods', Reliable Computing 5, 3-12,
> 1999 )
>
> It is found by gradient evaluation that the function is
> monotonic along
> each variable. (I computed gradients using 'gradientinit' tool of
> INTVAL toolbox for MATLAB of Rump etal).
> The gradients of f(x1,x2,x3) are found to be ---
>
> intval gradient derivative(s) yg.dx =
> Column 1
> [ -4.890465660975971e-001, -2.093516938447799e-001]
> Column 2
> [ 9.255280249313442e+000, 2.113569763264646e+001]
> Column 3
> [ -4.569281010721819e+001, -7.059391352010891e+000]
>
> It clearly shows monoticity of function along each variable, for
> the given input intervals x1,x2 and x3.
>
> 4) Though this may not happen for each function, the monotonicity check
> of the function f(X) for the given interval X (or may be parts of X)
> may obviously lead to more accurate and efficient computation
> of range.
>
> 5) I apologies, if I am wrong some where in my remarks, being a new user
> of interval arithmetic. And wel-come corrections, if any.
>
Of course in principle you are right to point this out. It also serves as an
example of one of the really powerful aspects of interval methods: if you
have several ways of testing things, you can pursue them all, and use the
most favorable result you get. The black magic lies in what routes to choose
to get you what you want most likely and most quickly.
>
> With regards
>
> **************************************************************************
> | J.J.Barve | also-- |
> | Research Scholar (Systems & Control) | Asst. Prof.-Instru. & Control |
> | Hostel-1, Room No. 243 | D.D.Institute of Tech.
> |
> | Indian Institute of Technology, Powai | NADIAD- 387 001
> |
> | Mumbai- 400 076 (INDIA) | Gujarat, INDIA
> |
> | Ph: 0091-022-769 2545-7887 | Ph: 0091-0268-61406
> |
> | E-mail: jjbarve [at] ee [dot] iitb.ernet.in | E-mail:
> barve [at] ddit [dot] ernet.in |
> **************************************************************************
>
>
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 10:48:31 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id KAA09619
for reliable_computing-outgoing; Wed, 17 Nov 1999 10:48:31 -0600 (CST)
Received: from pilot021.cl.msu.edu (pilot021.cl.msu.edu [35.9.5.121])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id KAA09614
for ; Wed, 17 Nov 1999 10:48:26 -0600 (CST)
Received: from berz (berz.user.msu.edu [35.10.52.114])
by pilot021.cl.msu.edu (8.9.1a/8.9.1) with SMTP id LAA23398;
Wed, 17 Nov 1999 11:47:31 -0500
From: "Martin Berz"
To: "Prof. P.S.V. Nataraj"
Cc: "vladik" , ,
,
"Makino Kyoko (NSCL)"
Subject: RE: methods with convergence order higher than two
Date: Wed, 17 Nov 1999 11:47:21 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
In-Reply-To:
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear Prof. Nataraj,
> -----Original Message-----
> From: owner-reliable_computing [at] interval [dot] usl.edu
> [mailto:owner-reliable_computing [at] interval [dot] usl.edu]On Behalf Of Prof.
> P.S.V. Nataraj
> Sent: Wednesday, November 17, 1999 1:04 AM
> To: Martin Berz
> Cc: vladik; rbk [at] usl [dot] edu; reliable_computing [at] interval [dot] usl.edu; Makino
> Kyoko (NSCL)
> Subject: RE: methods with convergence order higher than two
>
>
>
> Dear Dr. Berz,
>
> I have made a first reading of your papers on the Taylor model computation
> for multivariate functions.
>
> The Taylor model method appears to be quite promising in engineering
> applications such as ours, where there are several (upto 7-8) variables
> and functions can involve any of the built-in functions of FORTRAN.
>
> As I understand from your papers, the Taylor model computation can be
> done automatically even for high orders and a moderately large number
> of variables (both upto 10) using software available at your university.
>
yes, indeed something like 10 independent variables is not a problem.
> However, to be of general use in practical problems having thicker domain
> intervals (the examples in your papers have fairly thin domain
> intervals), it is necessary to combine the Taylor models with other
> schemes (at least, with sub-division) for range computation with higher
> order ( > 2) convergence.
As with any range bounding tool that works locally, for large domains this
method has to be applied repeatedly. In the case of the Taylor models, there
is usually a very sharp transition from which on they start to give very
good results, and so the "smallest" boxes one needs to manage can usually be
much larger than with intervals. So the "inflation" of boxes is usually much
less severe, and often one can just use a multidimensional grid and scan.
For the very difficult functions with lots of local maxima that we were
treating, this is usually what we did.
At one point we were actually starting to discuss with Baker to utilize the
Taylor models as a sharp local range bounding tool in his sophisticated
global optimizer, in which case one could use the whole machinery that
manages boxes etc; but so far this is only thought.
>
> Please tell if your univ's software for automatic Taylor model computation
> does support user defined routines having interval arithmetic
> operations?
>
yes, the COSY environment allows user-defined functions within the COSY
language very easily (or by linking to FORTRAN, which is a little more
difficult and system dependent), and we also support plain interval
evaluation.
> The idea is to be able to combine the Taylor model with
> sub-division, or use it along with more sophisticated interval
> global optimization techniques for efficient range computation over large
> boxes.
>
With separate message I was in contact with your student Mr. Barve, and I
suggest we try together to implement the functions you are interested in and
see what happens.
> Thanking you in advance,
>
> Regards,
>
> P.S.V. Nataraj
Sincerely,
Martin Berz
----------------------------------------------------------------------------
Prof. Dr. Martin Berz
Department of Physics and Astronomy
Michigan State University
East Lansing, MI 48824
517-333-6313 (Phone)
313-731-0313 (FAX)
berz [at] msu [dot] edu
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 14:25:22 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id OAA12976
for reliable_computing-outgoing; Wed, 17 Nov 1999 14:25:21 -0600 (CST)
Received: from pilot021.cl.msu.edu (pilot021.cl.msu.edu [35.9.5.121])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id OAA12944
for ; Wed, 17 Nov 1999 14:20:00 -0600 (CST)
Received: from berz (berz.user.msu.edu [35.10.52.114])
by pilot021.cl.msu.edu (8.9.1a/8.9.1) with SMTP id PAA85138;
Wed, 17 Nov 1999 15:14:14 -0500
From: "Martin Berz"
To: "R. Baker Kearfott" , "vladik"
Cc: ,
"Makino Kyoko (NSCL)"
Subject: RE: methods with convergence order higher than two
Date: Wed, 17 Nov 1999 15:14:03 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
In-Reply-To: <2.2.32.19991115030930.00742cb4 [at] pop [dot] usl.edu>
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Baker, Vladik, Sheela et al.,
Kyoko Makino has performed some runs with Taylor models for Baker's
problematic function; sorry that it took a while, I was almost out of
commission with an allergic reaction in the last two days. As we will show,
the Taylor model approach works very favorably even for this case. In fact,
we will use this example to illustrate the performance of the Taylor model
approach even for cases that are apparently nontrivial for conventional
interval methods.
>
> Martin,
>
> If I understand the process correctly, then I suspect that the
> method will not handle the following problem better than a low-order
> extension. (This problem is called
> Gritton's second problem, from chemical engineering.) I give the
> problem in the form of a Fortran statement for GlobSol. It is an
> eighteenth degree polynomial of one variable, and I present it in
> Horner's form.
>
> Am I right that a high-order Taylor model will not work better for
> this problem? (The function has 18 roots in the interval [-12,8].)
>
> Best regards,
>
> Baker
We study the behavior of Baker's function around the sample expansion point
1.0. The floating point Taylor expansion to order 5, as computed by COSY, is
as follows.
RDA evaluation of the function
RDA VARIABLE: NO= 5, NV= 1
I COEFFICIENT ORDER EXPONENTS
1 4.486589620246718 0 0
2 -8.799797859981823 1 1
3 -129.5969983611221 2 2
4 622.0452345235221 3 3
5 -914.5460853304157 4 4
6 -40.40649503718055 5 5
---------------------------------
(Baker, to make sure we have the right function, if you want you can see if
you get the same function value - we also ran the function in FORTRAN and it
checked out ok)
Kyoko computed the Taylor model remainder bound, a total bound predicted by
the Taylor model, a bound obtained by naive interval arithmetic, and to put
things into perspective as to what can be expected, an inner inclusion or
the range bound obtained by scanning the function over 1000 regularly spaced
points. All interval operations were performed using COSY's interval tools
based on software outward rounding, and the results are shown below for
reference.
We use the example to illustrate the following points.
1) Taylor models can give inclusions that are many orders of magnitude
sharper than those obtained by naive interval evaluation, even for examples
such as this that are considered complicated.
For example, for a width of 0.4, the width of the fifth order Taylor model
remainder bound is about 0.7, while the width of the naive interval bound is
around 20,000. As expected, with smaller widths, the results become more
favorable for Taylor models; at a width of 0.0125, the width of the fifth
order Taylor model remainder bound is about 5E-10, while the width of the
naive interval bound is around 400. Tenth order Taylor models behave even
much more favorable.
2) The sharpness of the prediction with Taylor models of order n scales with
order (n+1), the demand posed in the original question that lead to this
thread.
Indeed, in the example below using n=5, it can be observed that dividing the
width by two yields a gain of nearly two orders of magnitude, and over the
entire range of widths we have studied. Because n=5, as illustrated in my
reply to Vladik's summary of the method, all occurring polynomials can be
bounded fully sharply by mere arithmetic (which of course has to be done
with interval representations of floating point numbers, and thus introduces
a very small but for our purposes irrelevant overestimation), and thus the
sharpness of the remainder bound is a true measure for the sharpness of the
entire method.
Similarly, for n=10, we obtain a gain of about three orders of magnitude
each time the interval is divided by two. A sharpness of around 1E-12 is
reached for a domain of width 0.1.
3) Compared to the other effects, the details of what polynomial bounder is
being used is of rather secondary importance.
To illustrate this point, we purposely used neither the analytic bounder,
nor the one outlined in my message of Sunday. Rather, we merely sent
intervals through the respective polynomial, with the only sophistication
being the use of an intrinsic interval square operation where applicable. As
such, this method represents a rather crude lower bound of what to expect
from polynomial bounders.
Nevertheless, the resulting total bounds behave much more favorably with
Taylor models, providing an overestimation of about a factor of 2 for the
largest width studied (as opposed to an overestimation of a factor of 2,000
for the naive intervals), and reaching the noise level of the scanning
estimate, but certainly much less than 1.01 for the smallest width (as
opposed to an overestimation of a factor of 50 for the naive intervals)
4) To use naive intervals to achieve sharpness levels comparable to those
that can be attained with Taylor models requires domain widths many orders
of magnitude smaller.
To illustrate this effect, we list the widths of naive interval evaluations
of the function for various widths, showing the expected linear scaling.
Domain width Resulting width
0.1D+01 : 140666.8672350321
0.1D-01 : 356.3602597354367
0.1D-03 : 3.563758735169588
0.1D-05 : 0.3563758754273927E-01
0.1D-07 : 0.3563759053708537E-03
0.1D-09 : 0.3563790302862913E-05
0.1D-11 : 0.3567049766672881E-07
As usual, the effectiveness of the method is intimately tied to the fact
that the bulk behavior of the functional dependence is captured in the
Taylor expansion. In the example in question, there is a lot of cancellation
going on between the different orders of the original polynomial, which make
interval calculations difficult and lead to overestimation. In the Taylor
model approach, however, the Taylor models of the various terms of the
polynomial can be added and subtracted, and the bulk of the cancellation
problem disappears.
The detailed results of Kyoko's Taylor model computations are as follows.
*** Width 0.4000000000000000
REMAINDER BOUND INTERVAL
Order 5 [-.3416357780869606 ,0.3416357780869606 ]
Order 10 [-0.2328535934303353E-05, 0.2328535934303353E-05]
Bound evaluation of the function
Taylor Model: [ -9.251451355410341 , 11.57747692493020 ]
Naive Interval: [ -12562.21065212304 , 10660.56655625021 ]
Rastering: [ -5.273490704793460 , 4.617158578875092 ]
*** Width 0.2000000000000000
REMAINDER BOUND INTERVAL
Order 5 [-.4621661359731618E-002,0.4621661359731619E-002]
Order 10 [-0.1107624804821486E-08, 0.1107624804821485E-08]
Bound evaluation of the function
Taylor Model: [ 1.592114281270570 , 5.993640367078595 ]
Naive Interval: [ -4604.902777062254 , 3766.828066581296 ]
Rastering: [ 2.842020783777230 , 4.617163053028378 ]
*** Width 0.1000000000000000
REMAINDER BOUND INTERVAL
Order 5 [-.6726596225651657E-004,0.6726596225651657E-004]
Order 10 [-0.5340837667066269E-12, 0.5340837667066269E-12]
Bound evaluation of the function
Taylor Model: [ 3.639055771004044 , 5.004415060553268 ]
Naive Interval: [ -1942.104301934065 , 1832.828958028471 ]
Rastering: [ 3.794653671645733 , 4.617163892782912 ]
*** Width 0.5000000000000000E-01
REMAINDER BOUND INTERVAL
Order 5 [-.1014678358854022E-005,0.1014678358854024E-005]
Bound evaluation of the function
Taylor Model: [ 4.175518439144360 , 4.716305432808793 ]
Naive Interval: [ -901.0920355888309 , 904.9732440520786 ]
Rastering: [ 4.194958674398492 , 4.615510452684589 ]
*** Width 0.2500000000000000E-01
REMAINDER BOUND INTERVAL
Order 5 [-.1557890476201449E-007,0.1557890476201449E-007]
Bound evaluation of the function
Taylor Model: [ 4.355105328209006 , 4.597802053505219 ]
Naive Interval: [ -439.9913804625362 , 452.3847128010760 ]
Rastering: [ 4.357535212820721 , 4.575100319861519 ]
*** Width 0.1250000000000000E-01
REMAINDER BOUND INTERVAL
Order 5 [-.2413011037357702E-009,0.2413011037357716E-009]
Bound evaluation of the function
Taylor Model: [ 4.426375238247726 , 4.541740224010647 ]
Naive Interval: [ -217.5954692009348 , 227.8438762229445 ]
Rastering: [ 4.426678971590206 , 4.536372712588161 ]
Hope this helps -
Martin
>
>
> =====================================================================
> ! Using Horner's scheme --
>
> F(1) = -0.371936250000000D+03 + X(1)* ( &
> -0.791246565600000D+03 + X(1)* ( &
> 0.404494414300000D+04 + X(1)* ( &
> 0.978137516700000D+03 + X(1)* ( &
> -0.165478928000000D+05 + X(1)* ( &
> 0.221407282700000D+05 + X(1)* ( &
> -0.932654935900000D+04 + X(1)* ( &
> -0.351853687200000D+04 + X(1)* ( &
> 0.478253229600000D+04 + X(1)* ( &
> -0.128147944000000D+04 + X(1)* ( &
> -0.283443587500000D+03 + X(1)* ( &
> 0.202627091500000D+03 + X(1)* ( &
> -0.161791345900000D+02 + X(1)* ( &
> -0.888303902000000D+01 + X(1)* ( &
> 0.157558017300000D+01 + X(1)* ( &
> 0.124599084800000D+00 + X(1)* ( &
> -0.358914862200000D-01 + X(1)* ( &
> -0.195109557600000D-03 + X(1)* ( &
> 0.227468222900000D-03 ))))))))))))))))))
> =====================================================================
From owner-reliable_computing [at] interval [dot] usl.edu Wed Nov 17 18:53:57 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id SAA15426
for reliable_computing-outgoing; Wed, 17 Nov 1999 18:53:56 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id SAA15421
for ; Wed, 17 Nov 1999 18:53:53 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id SAA24961;
Wed, 17 Nov 1999 18:53:36 -0600 (CST)
Message-Id: <2.2.32.19991118005452.00731f90 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 17 Nov 1999 18:54:52 -0600
To: "Martin Berz" , "vladik"
From: "R. Baker Kearfott"
Subject: RE: methods with convergence order higher than two
Cc: ,
"Makino Kyoko (NSCL)"
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Martin,
Very nice. This does a lot to convince me of the approach's
usefulness :-)
Best regards,
Baker
At 03:14 PM 11/17/99 -0500, Martin Berz wrote:
>Baker, Vladik, Sheela et al.,
>
>Kyoko Makino has performed some runs with Taylor models for Baker's
>problematic function; sorry that it took a while, I was almost out of
>commission with an allergic reaction in the last two days. As we will show,
>the Taylor model approach works very favorably even for this case. In fact,
>we will use this example to illustrate the performance of the Taylor model
>approach even for cases that are apparently nontrivial for conventional
>interval methods.
>
>
>>
>> Martin,
>>
>> If I understand the process correctly, then I suspect that the
>> method will not handle the following problem better than a low-order
>> extension. (This problem is called
>> Gritton's second problem, from chemical engineering.) I give the
>> problem in the form of a Fortran statement for GlobSol. It is an
>> eighteenth degree polynomial of one variable, and I present it in
>> Horner's form.
>>
>> Am I right that a high-order Taylor model will not work better for
>> this problem? (The function has 18 roots in the interval [-12,8].)
>>
>> Best regards,
>>
>> Baker
>
>We study the behavior of Baker's function around the sample expansion point
>1.0. The floating point Taylor expansion to order 5, as computed by COSY, is
>as follows.
>
>
> RDA evaluation of the function
> RDA VARIABLE: NO= 5, NV= 1
> I COEFFICIENT ORDER EXPONENTS
> 1 4.486589620246718 0 0
> 2 -8.799797859981823 1 1
> 3 -129.5969983611221 2 2
> 4 622.0452345235221 3 3
> 5 -914.5460853304157 4 4
> 6 -40.40649503718055 5 5
> ---------------------------------
>
>(Baker, to make sure we have the right function, if you want you can see if
>you get the same function value - we also ran the function in FORTRAN and it
>checked out ok)
>
>Kyoko computed the Taylor model remainder bound, a total bound predicted by
>the Taylor model, a bound obtained by naive interval arithmetic, and to put
>things into perspective as to what can be expected, an inner inclusion or
>the range bound obtained by scanning the function over 1000 regularly spaced
>points. All interval operations were performed using COSY's interval tools
>based on software outward rounding, and the results are shown below for
>reference.
>
>We use the example to illustrate the following points.
>
>1) Taylor models can give inclusions that are many orders of magnitude
>sharper than those obtained by naive interval evaluation, even for examples
>such as this that are considered complicated.
>
>For example, for a width of 0.4, the width of the fifth order Taylor model
>remainder bound is about 0.7, while the width of the naive interval bound is
>around 20,000. As expected, with smaller widths, the results become more
>favorable for Taylor models; at a width of 0.0125, the width of the fifth
>order Taylor model remainder bound is about 5E-10, while the width of the
>naive interval bound is around 400. Tenth order Taylor models behave even
>much more favorable.
>
>
>2) The sharpness of the prediction with Taylor models of order n scales with
>order (n+1), the demand posed in the original question that lead to this
>thread.
>
>Indeed, in the example below using n=5, it can be observed that dividing the
>width by two yields a gain of nearly two orders of magnitude, and over the
>entire range of widths we have studied. Because n=5, as illustrated in my
>reply to Vladik's summary of the method, all occurring polynomials can be
>bounded fully sharply by mere arithmetic (which of course has to be done
>with interval representations of floating point numbers, and thus introduces
>a very small but for our purposes irrelevant overestimation), and thus the
>sharpness of the remainder bound is a true measure for the sharpness of the
>entire method.
>
>Similarly, for n=10, we obtain a gain of about three orders of magnitude
>each time the interval is divided by two. A sharpness of around 1E-12 is
>reached for a domain of width 0.1.
>
>
>3) Compared to the other effects, the details of what polynomial bounder is
>being used is of rather secondary importance.
>
>To illustrate this point, we purposely used neither the analytic bounder,
>nor the one outlined in my message of Sunday. Rather, we merely sent
>intervals through the respective polynomial, with the only sophistication
>being the use of an intrinsic interval square operation where applicable. As
>such, this method represents a rather crude lower bound of what to expect
>from polynomial bounders.
>
>Nevertheless, the resulting total bounds behave much more favorably with
>Taylor models, providing an overestimation of about a factor of 2 for the
>largest width studied (as opposed to an overestimation of a factor of 2,000
>for the naive intervals), and reaching the noise level of the scanning
>estimate, but certainly much less than 1.01 for the smallest width (as
>opposed to an overestimation of a factor of 50 for the naive intervals)
>
>
>4) To use naive intervals to achieve sharpness levels comparable to those
>that can be attained with Taylor models requires domain widths many orders
>of magnitude smaller.
>
>To illustrate this effect, we list the widths of naive interval evaluations
>of the function for various widths, showing the expected linear scaling.
>
> Domain width Resulting width
>
> 0.1D+01 : 140666.8672350321
> 0.1D-01 : 356.3602597354367
> 0.1D-03 : 3.563758735169588
> 0.1D-05 : 0.3563758754273927E-01
> 0.1D-07 : 0.3563759053708537E-03
> 0.1D-09 : 0.3563790302862913E-05
> 0.1D-11 : 0.3567049766672881E-07
>
>
>As usual, the effectiveness of the method is intimately tied to the fact
>that the bulk behavior of the functional dependence is captured in the
>Taylor expansion. In the example in question, there is a lot of cancellation
>going on between the different orders of the original polynomial, which make
>interval calculations difficult and lead to overestimation. In the Taylor
>model approach, however, the Taylor models of the various terms of the
>polynomial can be added and subtracted, and the bulk of the cancellation
>problem disappears.
>
>The detailed results of Kyoko's Taylor model computations are as follows.
>
>*** Width 0.4000000000000000
>
> REMAINDER BOUND INTERVAL
> Order 5 [-.3416357780869606 ,0.3416357780869606 ]
> Order 10 [-0.2328535934303353E-05, 0.2328535934303353E-05]
>
> Bound evaluation of the function
> Taylor Model: [ -9.251451355410341 , 11.57747692493020 ]
> Naive Interval: [ -12562.21065212304 , 10660.56655625021 ]
> Rastering: [ -5.273490704793460 , 4.617158578875092 ]
>
>*** Width 0.2000000000000000
>
> REMAINDER BOUND INTERVAL
> Order 5 [-.4621661359731618E-002,0.4621661359731619E-002]
> Order 10 [-0.1107624804821486E-08, 0.1107624804821485E-08]
>
>Bound evaluation of the function
> Taylor Model: [ 1.592114281270570 , 5.993640367078595 ]
> Naive Interval: [ -4604.902777062254 , 3766.828066581296 ]
> Rastering: [ 2.842020783777230 , 4.617163053028378 ]
>
>*** Width 0.1000000000000000
>
> REMAINDER BOUND INTERVAL
> Order 5 [-.6726596225651657E-004,0.6726596225651657E-004]
> Order 10 [-0.5340837667066269E-12, 0.5340837667066269E-12]
>
> Bound evaluation of the function
> Taylor Model: [ 3.639055771004044 , 5.004415060553268 ]
> Naive Interval: [ -1942.104301934065 , 1832.828958028471 ]
> Rastering: [ 3.794653671645733 , 4.617163892782912 ]
>
>*** Width 0.5000000000000000E-01
> REMAINDER BOUND INTERVAL
> Order 5 [-.1014678358854022E-005,0.1014678358854024E-005]
>
> Bound evaluation of the function
> Taylor Model: [ 4.175518439144360 , 4.716305432808793 ]
> Naive Interval: [ -901.0920355888309 , 904.9732440520786 ]
> Rastering: [ 4.194958674398492 , 4.615510452684589 ]
>
>*** Width 0.2500000000000000E-01
>
> REMAINDER BOUND INTERVAL
> Order 5 [-.1557890476201449E-007,0.1557890476201449E-007]
>
> Bound evaluation of the function
> Taylor Model: [ 4.355105328209006 , 4.597802053505219 ]
> Naive Interval: [ -439.9913804625362 , 452.3847128010760 ]
> Rastering: [ 4.357535212820721 , 4.575100319861519 ]
>
>*** Width 0.1250000000000000E-01
>
> REMAINDER BOUND INTERVAL
> Order 5 [-.2413011037357702E-009,0.2413011037357716E-009]
>
> Bound evaluation of the function
> Taylor Model: [ 4.426375238247726 , 4.541740224010647 ]
> Naive Interval: [ -217.5954692009348 , 227.8438762229445 ]
> Rastering: [ 4.426678971590206 , 4.536372712588161 ]
>
>
>Hope this helps -
>
>Martin
>
>
>>
>>
>> =====================================================================
>> ! Using Horner's scheme --
>>
>> F(1) = -0.371936250000000D+03 + X(1)* ( &
>> -0.791246565600000D+03 + X(1)* ( &
>> 0.404494414300000D+04 + X(1)* ( &
>> 0.978137516700000D+03 + X(1)* ( &
>> -0.165478928000000D+05 + X(1)* ( &
>> 0.221407282700000D+05 + X(1)* ( &
>> -0.932654935900000D+04 + X(1)* ( &
>> -0.351853687200000D+04 + X(1)* ( &
>> 0.478253229600000D+04 + X(1)* ( &
>> -0.128147944000000D+04 + X(1)* ( &
>> -0.283443587500000D+03 + X(1)* ( &
>> 0.202627091500000D+03 + X(1)* ( &
>> -0.161791345900000D+02 + X(1)* ( &
>> -0.888303902000000D+01 + X(1)* ( &
>> 0.157558017300000D+01 + X(1)* ( &
>> 0.124599084800000D+00 + X(1)* ( &
>> -0.358914862200000D-01 + X(1)* ( &
>> -0.195109557600000D-03 + X(1)* ( &
>> 0.227468222900000D-03 ))))))))))))))))))
>> =====================================================================
>
>
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Thu Nov 18 23:26:42 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id XAA17997
for reliable_computing-outgoing; Thu, 18 Nov 1999 23:26:42 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id XAA17992
for ; Thu, 18 Nov 1999 23:26:38 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id WAA00779
for ; Thu, 18 Nov 1999 22:26:32 -0700 (MST)
Message-Id: <199911190526.WAA00779 [at] cs [dot] utep.edu>
Date: Thu, 18 Nov 1999 22:26:31 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: edited book on measurements: a message from L. Reznik
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: iqm5W9YRkrliEUyq808anw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
FYI: interval computations in measurements is a possible topic (see details
below)
------------- Begin Forwarded Message -------------
November 9, 1999
Dear Madam/Sir
I have been commissioned by Physica-Verlag (a Springer-Verlag
Company), Heidelberg, Germany to prepare the edited volume:
"Soft computing in measurement and information acquisition" ( Note
that the title is provisional and could be changed at the later stage)
which is meant to appear in the series "Studies in Soft Computing and
Fuzziness" published by Physica-Verlag, Heidelberg - New York and
distributed world-wide via the huge Springer-Verlag distribution
system. You might like to see more information about this series and
its other volumes on the Springer Verlag home page
(http://www.springer.de/cgi-bin/search_book.pl?series=2941) or request
it from any Springer representative around the world.
We adopt here a broad definition of soft computing as a synergism of
methodologies of fuzzy logic, neural computing, genetic/evolutionary
programming, probabilistic reasoning, interval analysis, belief
networks, chaos theory and parts of learning theory. Soft computing
differs from conventional (hard) computing in that, unlike hard
computing, it is tolerant of imprecision, uncertainty, partial truth,
and approximation. These features are exactly what any real-life
information usually has. In this volume we are interested in new
models and methods which could be applied for information acquisition
with a proper reference to its uncertainty.
The volume is assumed to become a broad, up-to-date, and
state-of-the-art coverage of very diverse aspects related to the
use of soft computing methodologies and related techniques in broadly
perceived acquisition of information of various nature: technological,
socioeconomic, etc. We would like to include papers on quantitative
measurement and sensor design, qualitative measurements and their
applications in organisational, business and information
systems. Especially we are interested in presenting new methods and
models of various kinds of information fusion.
We think about a volume devoted to an application of soft computing
methods and models in information acquisition. Information is assumed
in a wide sense, starting from real results coming from measurement
and up to expert's forecast.
The particular chapters of the volume will be written by leading
scholars and researchers from all parts of the world. We would be very
interested in having you contribute to this volume by writing a
chapter based upon your expertise, and current interests and
activities.
If you wish, you may submit more than one proposal of your
potential contribution, each with a short abstract, so that we
could choose. Moreover, we would appreciate receiving from you any
comments, suggestions, etc. related to the volume.
The volume is expected to appear in the first half of 2001. In order
to make it happen we would like to receive your first response as soon
as possible. Please, send us the proposed title (could be changed
slightly later), the list of authors and their affiliations and a
brief abstract (one-two paragraphs) not later that the 15th of
January, 2000. Of course, we would be very grateful to receive this
information earlier. Based on this information we would be able to
compile the volume contents. We have to contact you by the end of
January, 2000 with a confirmation of your paper inclusion into this
volume and instructions for your paper preparation. We will expect the
full text of your paper by the 30th of May, 2000. As a rule, papers
should not exceed 20 pages, however, since we expect to have many
excellent papers and a limit on the number of pages, we would
appreciate if you could keep your paper(s) as short as possible (in
particular, avoid discussing well known issues or those which may be
dealt with in other papers of the volume). Your manuscript may either
need no corrections or changes, and hence will be considered
camera-ready, or otherwise we will contact you and request a corrected
version. Therefore, to speed up the editorial process, and avoid
requesting the authors to introduce irrelevant, small changes, we
would need a diskette with your article. Sending your manuscript by
Email could be possible as well.
Then, the editorial work will be done by the editors and publishers,
and the volume will appear in the first half of 2001. Each first
author will receive a complimentary copy of the volume.
Let me once again provide you with our publication time table:
Invitation to the potential contributors November 1999
Indication of interest by the contributors 15th of January 2000
Preliminary confirmation of paper inclusion 30th of January 2000
Full text of the paper 30th of May 2000
Editorial work and final confirmation 30th of September 2000
Publication 1st half of 2001
As you may see, our schedule is tight but since the timeliness is
very important for the success of our editorial project, we are
looking forward to your kind consideration and efforts to adhere
to the above given deadlines.
We are looking forward to hearing from you and receiving your
indication of interest as soon as possible, and to a fruitful further
collaboration in this exciting editorial project.
With best wishes and regards,
Sincerely yours,
Dr. Leonid Reznik
School of Communications and Informatics
Victoria University of Technology - F119
P.O.Box 14428 Melbourne City MC VIC 8001 Australia
Pnone: +(613) 9688 4079
Fax: +(613) 9688 4908
Email: leonid [at] cabsav [dot] vu.edu.au
------------- End Forwarded Message -------------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 20 07:13:51 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id HAA00389
for reliable_computing-outgoing; Sat, 20 Nov 1999 07:13:51 -0600 (CST)
Received: from mercury.Sun.COM (mercury.Sun.COM [192.9.25.1])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id HAA00384
for ; Sat, 20 Nov 1999 07:13:27 -0600 (CST)
Received: from Holland.Sun.COM ([129.159.201.1])
by mercury.Sun.COM (8.9.3+Sun/8.9.3) with SMTP id FAA01094;
Sat, 20 Nov 1999 05:13:20 -0800 (PST)
Received: from romulus by Holland.Sun.COM (SMI-8.6/SMI-SVR4-sd.fkk200)
id OAA00306; Sat, 20 Nov 1999 14:13:18 +0100
Received: from diamond by romulus (SMI-8.6/SMI-SVR4-su.fkk202)
id OAA23292; Sat, 20 Nov 1999 14:13:19 +0100
Message-Id: <199911201313.OAA23292@romulus>
Date: Sat, 20 Nov 1999 14:13:22 +0100 (MET)
From: Jan Boerhout
Reply-To: Jan Boerhout
Subject: Probabilistic Weather Forecasting and Interval Arithmetic
To: reliable_computing [at] interval [dot] usl.edu, validated_numerics@tu-harburg.de,
interval [at] cs [dot] utep.edu
Cc: bill.walster [at] eng [dot] sun.com
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 9meSTvcx5DI6zQFL9vO1UQ==
X-Mailer: dtmail 1.3.0 CDE Version 1.3 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Dear members of the "Interval Arithmetic Community",
Last week I addressed a group of Numerical Weather Prediction (NWP) and
Climatology experts to make them aware of interval arithmetic compiler
support and asking them to comment on possible applicability in this area
(see mail attached).
Bill Walster suggested I post it also on your alias to find NWP experts
in the interval community.
Any comments on interval arithmetic in NWP/Climatology are highly
appreciated.
In anticipation, thank you for your time.
Regards,
Jan
-----------------------------------------------------------------
Jan Boerhout jan.boerhout [at] holland [dot] sun.com
Sun Microsystems Phone +31 6 20139684
EMEA HPC Team http://www.holland/~jb84589 (Sun intranet)
-----------------------------------------------------------------
Dear Sirs,
During this week's ECMWF's Workshop on Meteorological Operational
Systems I learned about the significance of probabilistic forecasting.
The impact on computational requirements seems considerable, even
for ensembles of moderate size.
There may be a possibility to aleviate this by taking advantage of a
new compiler feature: interval arithmetic. Instead of representing
specific variables/arrays as point values, a range is assigned.
Performing the required computations on ranges, or intervals,
instead of point values, the results will also be represented by an
interval.
Error propagation is only one application of interval arithmetic.
Another is global optimization, where function properties in
argument intervals are used to find minima/maxima.
Looking at the perturbation technique for the generation of forecast
ensembles, it occurred to me that it might be possible to benefit
from interval arithmetic.
Though the technique itself is not new, compiler support for it is.
Would you please be so kind as to give this new possibility some
thought. Our interval arithmetic expert, Mr. William Walster, would
be very happy to help evaluate the potential for meteorological
and/or climatological modeling. Though he is not a meteorological
expert, he would be very interested in learning more about the
issues in your area of expertise. Mr. Walster resigned his full
professorship at the University of Wisconsin, Madison to get an
interval compiler in industry.
For further reference, please find attached a list of URLs to papers
written and talks given on interval arithmetic in various other
application areas.
Should you require more specific information, please do not hesitate
to contact me.
We value your comments highly.
Yours sincerely,
Jan Boerhout
HPC Specialist
URLs:
http://www.mscs.mu.edu/~globsol
http://www.delisoft.fi/
http://www.peda.com/grafeq/
http://cs.utep.edu/interval-comp/
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 21 21:07:57 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id VAA03086
for reliable_computing-outgoing; Sun, 21 Nov 1999 21:07:57 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id VAA03081
for ; Sun, 21 Nov 1999 21:07:54 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id UAA11954
for ; Sun, 21 Nov 1999 20:07:34 -0700 (MST)
Message-Id: <199911220307.UAA11954 [at] cs [dot] utep.edu>
Date: Sun, 21 Nov 1999 20:07:34 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: from NA Digest
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 5a8yscfxVq7JCEjmuN2dLQ==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
From: Siegfried Rump
Date: Fri, 19 Nov 1999 13:33:41 +-100
Subject: A MATLAB Library for Interval Arithmetic
This is to announce version 3 of
INTLAB - A Matlab library for interval arithmetic routines.
Version 3 covers
- interval arithmetic for real and complex data including vectors
and matrices (very fast),
- interval arithmetic for real and complex sparse matrices (very fast),
- automatic differentiation (forward mode, vectorized computations, fast),
- automatic slopes (sequential approach, slow for many variables),
- rigorous real interval standard functions (fast, very accurate, 3 ulps),
- rigorous complex interval standard functions (fast, rigorous, but not
necessarily sharp inclusions),
- rigorous input/output,
- multiple precision interval arithmetic with error bounds (does the job,
slow)
and more. Prerequisite is Matlab 5+. All INTLAB code is written in Matlab
except one routine for switching the rounding mode (the latter even being
superflous for Matlab 6 under Windows).
An example is (timing on a 120 MHz Laptop)
>> format long; rand('state',0)
>> n=200; A=2*rand(n)-1; b=A*ones(n,1);
>> tic, x=A\b; toc, x(1:5),
>> tic, X=intval(A)\b; toc, X(1:5)
elapsed_time =
0.59999999999999
ans =
1.00000000000000
1.00000000000004
1.00000000000003
1.00000000000003
0.99999999999999
elapsed_time =
3.52000000000000
intval ans =
1.00000000000___
1.00000000000___
1.000000000000__
1.00000000000___
1.00000000000___
Major objective is speed and ease of use. Algorithms are fast if high-order
operations can be used; nonlinear function evaluation slows down significantly
due to interpretation overhead and extensive use of operator concept.
For more details and downloading see
http://www.ti3.tu-harburg.de/rump/intlab/
Comments appreciated.
With best regards,
Siegfried M. Rump
From owner-reliable_computing [at] interval [dot] usl.edu Fri Nov 26 20:06:42 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id UAA03952
for reliable_computing-outgoing; Fri, 26 Nov 1999 20:06:42 -0600 (CST)
Received: from marnier.ucs.usl.edu (root@ucs-gw.usl.edu [130.70.40.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id UAA03947
for ; Fri, 26 Nov 1999 20:06:23 -0600 (CST)
Received: from u8174 (rbk5287 [at] goedel [dot] usl.edu [130.70.49.203])
by marnier.ucs.usl.edu (8.9.1/8.9.1/ucs-mx-host_1.3) with SMTP id UAA22233
for ; Fri, 26 Nov 1999 20:06:12 -0600 (CST)
Message-Id: <2.2.32.19991127020730.00688e10 [at] pop [dot] usl.edu>
X-Sender: rbk5287 [at] pop [dot] usl.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 26 Nov 1999 20:07:30 -0600
To: reliable_computing [at] interval [dot] louisiana.edu
From: "R. Baker Kearfott"
Subject: New GlobSol version posted
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Colleagues,
I have posted a new version of GlobSol, that can be obtained from the
link
http://interval.louisiana.edu/GlobSol/download_GlobSol.html
The main changes are two bug fixes, dealing with the way the lists
of solution boxes are handled. (I wish to thank Prof. Csendes' group
for finding the bug as described in #3 below.)
Here is the relevant excerpt from the release notes:
================================================================
Nov. 25, 1999 -- Differences between the version dated
July 22 and the version dated Nov. 25:
1. The list complementation process has been modified to
remove a bug. In particular, before the fix, the following
could have happened: a large verified box is put on the
list.
Subsequently, a smaller verified box corresponding to the
same solution is put on the list, and the original box is
complemented. When the original box is complemented, the
resulting boxes do not contain verified solutions. The fix
is to place the box fragments from the verified list onto
the unknown list. The occurrence of this problem is rare.
2. There have been minor adjustments to the makefiles.
3. An additional bug dealing with the complementation process
was fixed. Before, occasionally, an approximate feasible
point was found, and the verified list and completed list
were complemented, removing true solutions. Subsequent
processing of the approximate feasible point with an
interval Newton method revealed it contained no feasible
point, and the box was not stored. Thus, solutions were
lost. (The solutions in such cases were with active bound
constraints, and the box without a feasible point was
considered an interior box.)
4. A new test was added to the integration test suite.
5. An additional post-processing step, to move boxes from the
list of small boxes to the list of verified boxes, was
added.
NOTE: The integration tests were not run this time with
the NAG compiler on Sun machines, due to temporary
unavailability. Please report any problems you may
have with this compiler/OS combination, with this
release.
==================================================================
Sincerely,
Baker
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] usl.edu Sat Nov 27 23:38:07 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id XAA05382
for reliable_computing-outgoing; Sat, 27 Nov 1999 23:38:07 -0600 (CST)
Received: from unknown (1Cust38.tnt2.atl2.da.uu.net [63.22.15.38])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id XAA05367;
Sat, 27 Nov 1999 23:37:55 -0600 (CST)
From: bmark [at] atlantaoffice [dot] com
Subject: laser printer toner advertisement
Date: Sun, 28 Nov 1999 09:25:10
Message-Id: <894.177768.809912@>
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
BENCHMARK SUPPLY
7540 BRIDGEGATE COURT
ATLANTA GA 30350
***LASER PRINTER TONER CARTRIDGES***
***FAX AND COPIER TONER***
CHECK OUT OUR NEW CARTRIDGE PRICES :
APPLE
LASER WRITER PRO 600 OR 16/600 $69
LASER WRITER SELECT 300,310.360 $69
LASER WRITER 300, 320 $54
LASER WRITER LS,NT,2NTX,2F,2G & 2SC $54
LASER WRITER 12/640 $79
HEWLETT PACKARD
LASERJET SERIES 2,3 & 3D (95A) $49
LASERJET SERIES 2P AND 3P (75A) $54
LASERJET SERIES 3SI AND 4SI (91A) $75
LASERJET SERIES 4L AND 4P $49
LASERJET SERIES 4, 4M, 5, 5M, 4+ (98A) $59
LASERJET SERIES 4000 HIGH YIELD (27X) $99
LASERJET SERIES 4V $95
LASERJET SERIES 5SI , 8000 $95
LASERJET SERIES 5L AND 6L $49
LASERJET SERIES 5P, 5MP, 6P, 6MP $59
LASERJET SERIES 5000 (29A) $135
LASERJET SERIES 1100 (92A) $49
LASERJET SERIES 2100 (96A) $89
LASERJET SERIES 8100 (82X) $145
HP LASERFAX
LASERFAX 500, 700, FX1, $59
LASERFAX 5000, 7000, FX2, $59
LASERFAX FX3 $69
LASERFAX FX4 $79
LEXMARK
OPTRA 4019, 4029 HIGH YIELD $135
OPTRA R, 4039, 4049 HIGH YIELD $135
OPTRA S 4059 HIGH YIELD $135
OPTRA E $59
OPTRA N $115
EPSON
EPL-7000, 8000 $105
EPL-1000, 1500 $105
CANON
LBP-430 $49
LBP-460, 465 $59
LBP-8 II $54
LBP-LX $54
LBP-MX $95
LBP-AX $49
LBP-EX $59
LBP-SX $49
LBP-BX $95
LBP-PX $49
LBP-WX $95
LBP-VX $59
CANON FAX L700 THRU L790 FX1 $59
CANONFAX L5000 L70000 FX2 $59
CANON COPIERS
PC 20, 25 ETC.... $89
PC 3, 6RE, 7, 11 (A30) $69
PC 320 THRU 780 (E40) $89
NEC
SERIES 2 LASER MODEL 90,95 $105
PLEASE NOTE:
1) ALL OUR CARTRIDGES ARE GENUINE OEM CARTRIDGES.
2) WE DO NOT SEND OUT CATALOGS OR PRICE LISTS
3) WE DO NOT FAX QUOTES OR PRICE LISTS.
4) WE DO NOT SELL TO RESELLERS OR BUY FROM DISTRIBUTERS
5) WE DO NOT CARRY: BROTHER-MINOLTA-KYOSERA-PANASONIC PRODUCTS
6) WE DO NOT CARRY: XEROX-FUJITSU-OKIDATA OR SHARP PRODUCTS
7) WE DO NOT CARRY ANY COLOR PRINTER SUPPLIES
8) WE DO NOT CARRY DESKJET/INKJET OR BUBBLEJET SUPPLIES
9) WE DO NOT BUY FROM OR SELL TO RECYCLERS OR REMANUFACTURERS
WE ACCEPT GOVERNMENT, SCHOOL & UNIVERSITY PURCHASE ORDERS
JUST LEAVE YOUR PO # WITH CORRECT BILLING & SHIPPING ADDRESS
****OUR ORDER LINE IS 770-399-0953 ****
****OUR CUSTOMER SERVICE LINE IS 800-586-0540****
****OUR E-MAIL REMOVAL AND COMPLAINT LINE IS 888-494-8597****
****PLACE YOUR ORDER AS FOLLOWS**** :
BY PHONE 770-399-0953
BY FAX: 770-698-9700
BY MAIL: BENCHMARK PRINT SUPPLY
7540 BRIDGEGATE COURT
, ATLANTA GA 30350
MAKE SURE YOU INCLUDE THE FOLLOWING INFORMATION IN YOUR ORDER:
1) YOUR PHONE NUMBER
2) COMPANY NAME
3) SHIPPING ADDRESS
4) YOUR NAME
5) ITEMS NEEDED WITH QUANTITIES
6) METHOD OF PAYMENT. (COD OR CREDIT CARD)
7) CREDIT CARD NUMBER WITH EXPIRATION DATE
1) WE SHIP UPS GROUND. ADD $4.5 FOR SHIPPING AND HANDLING.
2) COD CHECK ORDERS ADD $3.5 TO YOUR SHIPPING COST.
2) WE ACCEPT ALL MAJOR CREDIT CARD OR "COD" ORDERS.
3) OUR STANDARD MERCHANDISE REFUND POLICY IS NET 30 DAYS
4) OUR STANDARD MERCHANDISE REPLCAMENT POLICY IS NET 90 DAYS.
NOTE NUMBER (1):
PLEASE DO NOT CALL OUR ORDER LINE TO REMOVE YOUR E-MAIL
ADDRESS OR COMPLAIN. OUR ORDER LINE IS NOT SETUP TO FORWARD
YOUR E-MAIL ADDRESS REMOVAL REQUESTS OR PROCESS YOUR
COMPLAINTS..IT WOULD BE A WASTED PHONE CALL.YOUR ADDRESS
WOULD NOT BE REMOVED AND YOUR COMPLAINTS WOULD NOT BE
HANDLED.PLEASE CALL OUR TOLL FREE E-MAIL REMOVAL AND
COMPLAINT LINE TO DO THAT.
NOTE NUMBER (2):
OUR E-MAIL RETURN ADDRESS IS NOT SETUP TO ANSWER ANY
QUESTIONS YOU MIGHT HAVE REGARDING OUR PRODUCTS. OUR E-MAIL
RETURN ADDRESS IS ALSO NOT SETUP TO TAKE ANY ORDERS AT
THIS TIME. PLEASE CALL THE ORDER LINE TO PLACE YOUR ORDER
OR HAVE ANY QUESTIONS ANSWERED. OTHERWISE PLEASE CALL OUR
CUSTOMER SERCICE LINE.
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 28 17:24:55 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id RAA07576
for reliable_computing-outgoing; Sun, 28 Nov 1999 17:24:55 -0600 (CST)
Received: from cs.utep.edu (galaxy.cs.utep.edu [129.108.5.2])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id RAA07571
for ; Sun, 28 Nov 1999 17:24:49 -0600 (CST)
Received: from earth.cs.utep.edu (earth.cs.utep.edu [129.108.5.21])
by cs.utep.edu (8.9.3/8.9.3) with SMTP id QAA11300
for ; Sun, 28 Nov 1999 16:24:46 -0700 (MST)
Message-Id: <199911282324.QAA11300 [at] cs [dot] utep.edu>
Date: Sun, 28 Nov 1999 16:24:45 -0700 (MST)
From: vladik
Reply-To: vladik
Subject: from NA Digest
To: reliable_computing [at] interval [dot] usl.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: vH4klVv/LpN1frHtwzSv3w==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.3.4 SunOS 5.7 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
From: Janos Pinter
Date: Mon, 22 Nov 1999 13:40:31 +0000
Subject: Global Optimization, Selected Case Studies
Dear Colleagues,
I have been in contact with Kluwer Academic Publishers regarding an
edited volume of case studies in global (nonconvex) optimization (GO).
The primary emphasis is on real-world applications - possibly including
also open problems - that apparently need genuine GO methodology.
It is planned that this volume will appear in the NOIA series. For currently
available books in the series, please see http://www.wkap.nl/series.htm/NOIA.
Potential contributors are asked to submit manuscripts based upon original
research. Manuscripts should be of 15-25 pages in length, following one of
the standard Kluwer AP styles. Kluwer stylefiles are available at
http://www.wkap.nl/kaphtml.htm/BOOKSTYLES.
There are four platforms to choose from: LaTeX, MS Word, WordPerfect, and
Scientific Workplace. Under each platform is a self-extracting (.exe) archive.
All contributions will be refereed. Upon acceptance, these will become
stand-alone chapters of the edited volume. I certainly plan to review all
contributions myself, but additional reviewer volunteers will be very much
appreciated. (They do not have to be - but can be - contributing authors,
of course.)
It would be good to complete work on this timely volume as soon as possible,
including the review process. Therefore I would like to ask contributors to
submit their work by May 31, 2000.
Potential contributors, please send a note that includes a tentative title
for your contribution. Reviewers, please send a note regarding areas within
GO you are willing to review.
Thank you in advance for your consideration of contributing to this volume.
Best regards,
Janos Pinter
From owner-reliable_computing [at] interval [dot] usl.edu Sun Nov 28 20:22:06 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id UAA08021
for reliable_computing-outgoing; Sun, 28 Nov 1999 20:22:06 -0600 (CST)
Received: from mscs.mu.edu (studsys.mscs.mu.edu [134.48.4.15])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id UAA08016
for ; Sun, 28 Nov 1999 20:22:03 -0600 (CST)
Received: (qmail 12528 invoked from network); 29 Nov 1999 02:21:08 -0000
Received: from ppp101.csd.mu.edu (HELO taylor) (134.48.24.1)
by studsys.mscs.mu.edu with SMTP; 29 Nov 1999 02:21:08 -0000
Message-ID: <005801bf3a10$5bff29c0$01183086@taylor>
From: "George Corliss"
To:
Subject: Fw: SCI'2000
Date: Sun, 28 Nov 1999 20:20:51 -0600
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 8bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Forwarding. Please forgive if this is a duplicate.
It would be good to have an interval presence there.
----- Original Message -----
From: Nagib Callaos
To:
Sent: Tuesday, November 16, 1999 8:06 AM
Subject: SCI'2000
CALL FOR PAPERS
THE 4TH WORLD MULTICONFERENCE ON
SYSTEMICS, CYBERNETICS AND INFORMATICS
SCI'2000
July, 23-26, 2000
Orlando, Florida(USA)
Sheraton World
http://www.iiis.org
Honorary Presidents: Bela Banathy, Stafford Beer and George Klir
Program Committee Chair: William Lesso
General Chair: Nagib Callaos
Organizing Committee Chair: Belkis Sanchez
MAJOR THEMES
* Information Systems Development
* Information Systems Management
* Management Information Systems
* Virtual Engineering
* Mobile/Wireless Computing
* Communication Systems and Networks
* Emergent Computation
* Image,Acoustic,Speech and Signal Processing
* Computing Techniques
* Human Information Systems
* Education and Information Systems
* Control Systems
* Economic and Financial Systems
* SCI in Biology and Medicine
* SCI in Psychology, Cognition and Spirituality
* Conceptual Infrastructure of SCI
* Natural Resources
* Human Resources
* Globalization, Development and Emerging Economies
* SCI in Art
ACADEMIC AND SCIENTIFIC CO-SPONSORS
· WOSC: World Organization on Systemics and Cybernetics (France)
· The Centre for Systems Studies (UK)
· Systems Society of Poland
· Society Applied Systems Research (Canada)
· Slovenian Artificial Intelligence Society
· Simon Bolivar University (Venezuela)
· Polish System Society (Poland)
· Italian Society of Systemics
· ISSS: International Society for the Systems Sciences (USA)
· ISI: The International Systems Institute (USA)
· IFSR: International Federation of Systems Research (Austria/USA)
· IEEE / Latinamerica
· Cybernetics and Human Knowing: A Journal of Second Order Cybernetics and
Cybersemiotics (Denmark)
· CUST, Engineer Science Institute of the Blaise Pascal University (France)
ORGANIZED BY THE IIIS
The International Institute of Informatics and Systemics.
ACTIVE PARTICIPATION
Those interested in participating in the:
· Organization of Invited Session(s)
· Organization of a Focus Symposium
· Reviewing Process
· Conference Promotion
· Recommending Scholars/Researchers for Active Participation and/or for
Papers Submissions.
· Proposing Organizations/Institutes/Universities as Academic/Scientific
Co-sponsors.
Please contact the General Chair Professor Nagib Callaos: ncallaos [at] callaos [dot] com
ncallaos@ aol.com
nacallao@
telcel.net.ve
PARTICIPANTS
Participation of both researchers and practitioners is strongly encouraged.
Papers may be
submitted on: research in science and engineering, case studies drawn on
professional
practice and consulting, and position papers based on large and rich
experience gained
through executive/managerial practices and decision-making. For this reason, the
Program Committee is conformed according to the criteria given above.
TYPES OF SUBMISSION ACCEPTED
1.Papers
* Research
* Review
* Position
* Report
2.Panel Presentation, Workshop and/or Round Table Proposals
3.New Topics and Invited Sessions Proposal(which should include a minimum
of 5 papers)
4.Focus Sympsia(which should include a minimum of 15 papers)
EXTENDED ABSTRACTS AND PAPER DRAFTS SUBMISSION FORM
Extended abstracts or paper drafts should be sent according the following
format:
1. Major theme of the paper, according the major themes given above.
2. Paper title.
3. Extended abstract of 500 to 1500 words and/or paper drafts of 2000 to
5000 words, in English.
4. Author or co-authors with names, addresses, telephone number, fax number
and e-mail address.
Extended abstracts or paper drafts should be sent via Internet, as
attachments to e-mails addressed
to nacallao [at] telcel [dot] net.ve and SCI2000 [at] aol [dot] com. Exceptionally, three copies
of extended abstracts or paper drafts
might be sent to the following postal mail address and/or faxed to the
following numbers:
IIIS
SCI '2000
7525 Karlov Avenue
Skokie, Illinois 60076
Fax Numbers:
1-407-8566274 (Orlando, USA)
58-2-9638852 (Caracas, Venezuela)
DEADLINES
December 16, 1999 Submission of extended abstracts (500-1500 words)or paper
draft(2000-2500 words)
Februray 29, 2000 Acceptance notifications
April 20, 2000 Submission of camera/ready papers: hard copies and
electronic versions
PAPERS REVIEWING AND PUBLICATION
Submitted papers will be refereed. Accepted papers, which should not exceed
six single-
spaced typed pages, will be published by means of paper and electronic
proceedings. The
full paper should be sent via Internet and by means of diskette and photoready
hard copies of artwork, not later than April 20, 2000.
Best papers will be selected for awards and recommended for journal
publications.
Multiple author books will be published by iiis, based on best-invited
sessions, best focus
symposia or best mini-conferences.
INVITED SESSIONS
To organize an invited session for SCI'2000, the following steps are suggested:
1) Identify a special topic is in the scope of SCI'2000. You may contact the
General chair,the Program Chair or other program committee members, on the
suitability of the topic, if
it is not included in the Conference Program.
2) Contact the General Chair for the invited session acceptation
3) Contact researchers or practitioners in your field to see if they can
contribute a paper to your proposed session and attend SCI'2000.
4) Collect the extended abstracts or the paper drafts from each perspective
invitee.
5) Write a summary (1-2 page) on the session's significance and coherence of
the invited/selected papers.
Mail the invited session proposal including a summary and a copy of all
abstracts before,
February 29,2000 to Professor Nagib Callaos, the General Chair.
PROGRAM COMMITTEE
Integrated by (210) prestigious scholars/researchers from 54 countries.
Details can be found in the conference web (http://www.iiis.org/isas/) page
or asking for a detailed Call For Papers, via e-mail.
CONFERENCE FEES
The conference fees will be $330 before April 11, 2000 and $380 after April
11, 2000.This fee will include:
* A CD-ROM version of the Proccedings
* One volumen of the hard copy version of the Conference Proceeding.
(Other volumes will be available with a 30% of discount for participants)
* Coffee breaks
* Welcome Reception
CONFERENCE CONTACTS
Prof. Nagib Callaos (General Chair)
E -mails: ncallaos@ usb.ve(Academic)
ncallaos@ aol.com(Personal)
ncallaos@ Callaos.com(Business)
ncallaos@ IIIS.com(IIIS)
USA Phone: +1
USA Fax: +1 (407) 856-6274
Venezuela Tel/Fax (office): +58 (2) 962-1519
Venezuela Tel/Fax (home): +58 (2) 963-8852
Conference Secretariat
SCI@ cantv.net
Other contacts and More details can be found at the
Conference web page (http://www.iiis.org/isas/). Answers to
specific questions can be requested also by e-mail.
Nagib Callaos, Ph.D.
Professor Simon Bolivar University
President IEEE/Computing Society (Venezuelan Section)
President IIIS Affiliated to the International Federation for Systems
Research (IFSR)
Venezuela: Tel/Fax: +(582)9638852 (home), +(582)9621519 (office)
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 29 02:27:23 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id CAA08598
for reliable_computing-outgoing; Mon, 29 Nov 1999 02:27:23 -0600 (CST)
Received: from mail.rwth-aachen.de (mail.RWTH-Aachen.DE [137.226.144.9])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id CAA08593
for ; Mon, 29 Nov 1999 02:27:19 -0600 (CST)
From: jarausch [at] igpm [dot] rwth-aachen.de
Received: from numa1.igpm.rwth-aachen.de by mail.rwth-aachen.de
(PMDF V5.1-12 #D3869) with ESMTP id <01JIWL54NMIM0007P2 [at] mail [dot] rwth-aachen.de>
for reliable_computing [at] interval [dot] usl.edu; Mon, 29 Nov 1999 09:29:00 +0100
Received: from igpm.rwth-aachen.de (localhost [127.0.0.1])
by numa1.igpm.rwth-aachen.de (980427.SGI.8.8.8/980728.SGI.AUTOCF)
via ESMTP id JAA92867 for ; Mon,
29 Nov 1999 09:27:12 +0100 (CST)
Date: Mon, 29 Nov 1999 09:27:09 +0100
Subject: Stiff ODE ?
To: reliable_computing [at] interval [dot] usl.edu
Reply-to: jarausch [at] igpm [dot] rwth-aachen.de
Message-id: <199911290827.JAA92867 [at] numa1 [dot] igpm.rwth-aachen.de>
MIME-version: 1.0
Content-type: TEXT/plain; charset=us-ascii
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Hi,
what is known about including solutions of stiff ODEs.
The initial inclusion in the approach I know about is equivalent to an
explicit Euler step and therefore not suitable for stiff systems.
Thank you for any pointers,
Helmut Jarausch
Lehrstuhl fuer Numerische Mathematik
Institute of Technology, RWTH Aachen
D 52056 Aachen, Germany
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 29 03:11:49 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id DAA08968
for reliable_computing-outgoing; Mon, 29 Nov 1999 03:11:49 -0600 (CST)
Received: from mscs.mu.edu (studsys.mscs.mu.edu [134.48.4.15])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with SMTP id DAA08963
for ; Mon, 29 Nov 1999 03:11:46 -0600 (CST)
Received: (qmail 3943 invoked from network); 29 Nov 1999 09:10:53 -0000
Received: from ppp108.csd.mu.edu (HELO taylor) (134.48.24.8)
by studsys.mscs.mu.edu with SMTP; 29 Nov 1999 09:10:53 -0000
Message-ID: <001401bf3a49$9919ed20$08183086@taylor>
From: "George Corliss"
To:
Cc:
References: <199911290827.JAA92867 [at] numa1 [dot] igpm.rwth-aachen.de>
Subject: Re: Stiff ODE ?
Date: Mon, 29 Nov 1999 03:10:35 -0600
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Helmut,
> what is known about including solutions of stiff ODEs.
> The initial inclusion in the approach I know about is equivalent to an
> explicit Euler step and therefore not suitable for stiff systems.
See the Work of Ned Nedialkov on Hermite-Obreshkov methods
Ned finished at Toronto last summer, and is now at McMaster.
His Toronto e-mail address is ned [at] cs [dot] toronto.edu
I do not seem to have is new address.
Once page I found is a paper abstract.
http://www.maths.uq.edu.au/~kb/scicade99/abstract/NedNedialkov8.html
You can find several of his reports at
http://www.cs.toronto.edu/NA/reports.html
Perhaps Ned will pick up on this response and contribute
current pointers.
You should also contact Markus Neher at the University of
Karlsruhe. He has done recent work on alternatives to the
explicit Euler stepsize control.
Note also that if you overcome the explicit Euler step
used for initial enclosure, the standard methods of Lohner,
Staunung, and Nedialkov perform better for stiff problems than
you might expect because in Algorithm II for tightening the
enclosure, they use similar Jacobian information to the
point methods for stiff problems.
George F. Corliss
Dept. Math, Stat, Comp Sci
Marquette University
P.O. Box 1881
Milwaukee, WI 53201-1881 USA
georgec [at] mscs [dot] mu.edu; George.Corliss [at] Marquette [dot] edu
http://www.mscs.mu.edu/~georgec/
Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472
From owner-reliable_computing [at] interval [dot] usl.edu Mon Nov 29 11:24:48 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id LAA09969
for reliable_computing-outgoing; Mon, 29 Nov 1999 11:24:47 -0600 (CST)
Received: from mcmail.cis.McMaster.CA (nedialk [at] mcmail [dot] CIS.McMaster.CA [130.113.64.66])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id LAA09964
for ; Mon, 29 Nov 1999 11:24:42 -0600 (CST)
Received: from localhost (nedialk@localhost)
by mcmail.cis.McMaster.CA with SMTP id MAA13418;
Mon, 29 Nov 1999 12:24:13 -0500 (EST)
Date: Mon, 29 Nov 1999 12:24:11 -0500 (EST)
From: Ned Nedialkov
To: reliable_computing [at] interval [dot] usl.edu
cc: jarausch [at] igpm [dot] rwth-aachen.de
Subject: Re: Stiff ODE ?
In-Reply-To: <99Nov29.120456edt.96310-61 [at] jane [dot] cs.toronto.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
I would add the following reference:
@PHDTHESIS
{
Gong1994a,
AUTHOR = "Gong, W.",
TITLE = "A Priori Inclusions for Solutions to Initial Value
Problems of Contractive {ODE}s",
SCHOOL = "Technische Universit{\"a}t",
ADDRESS = "Wien",
YEAR = "1994",
}
Ned
From owner-reliable_computing [at] interval [dot] usl.edu Tue Nov 30 13:00:47 1999
Received: (from root@localhost)
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) id NAA13103
for reliable_computing-outgoing; Tue, 30 Nov 1999 13:00:47 -0600 (CST)
Received: from mail.rwth-aachen.de (mail.RWTH-Aachen.DE [137.226.144.9])
by interval.usl.edu (8.9.1/8.9.1/interval-math-majordomo-1.0) with ESMTP id NAA13098
for ; Tue, 30 Nov 1999 13:00:42 -0600 (CST)
From: jarausch [at] igpm [dot] rwth-aachen.de
Received: from numa1.igpm.rwth-aachen.de by mail.rwth-aachen.de
(PMDF V5.1-12 #D3869) with ESMTP id <01JIY28L3IK4000DIW [at] mail [dot] rwth-aachen.de>
for reliable_computing [at] interval [dot] usl.edu; Tue, 30 Nov 1999 10:48:58 +0100
Received: from igpm.rwth-aachen.de (localhost [127.0.0.1])
by numa1.igpm.rwth-aachen.de (980427.SGI.8.8.8/980728.SGI.AUTOCF)
via ESMTP id KAA95343; Tue, 30 Nov 1999 10:46:28 +0100 (CST)
Date: Tue, 30 Nov 1999 10:46:25 +0100
Subject: Re: Stiff ODE ?
In-reply-to:
To: nedialk [at] mcmail [dot] cis.McMaster.CA
Cc: reliable_computing [at] interval [dot] usl.edu
Reply-to: jarausch [at] igpm [dot] rwth-aachen.de
Message-id: <199911300946.KAA95343 [at] numa1 [dot] igpm.rwth-aachen.de>
MIME-version: 1.0
Content-type: TEXT/plain; charset=us-ascii
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Many thanks!
Does anybody know an URL of this paper or an email of the author?
Thanks,
Helmut.
On 29 Nov, Ned Nedialkov wrote:
>
>
> I would add the following reference:
>
> @PHDTHESIS
> {
> Gong1994a,
> AUTHOR = "Gong, W.",
> TITLE = "A Priori Inclusions for Solutions to Initial Value
> Problems of Contractive {ODE}s",
> SCHOOL = "Technische Universit{\"a}t",
> ADDRESS = "Wien",
> YEAR = "1994",
> }
>
>
> Ned
--
Helmut Jarausch
Lehrstuhl fuer Numerische Mathematik
Institute of Technology, RWTH Aachen
D 52056 Aachen, Germany