Let us consider the following polynomial
f(x)=3D 240000 * x - 25000 * x^2 + 3500 * x^3/3 - 25*x^4 + =
x^5/5
and the interval [x]=3D[-1000, 1]
First derivative of the function f has the following form
d(1)f(x)=3D 240000-50000*x+3500* x*x-100*x*x*x+x*x*x*x;
Interval extension of this function is equal to:
d(1)f([-1000, 1]) =3D [-1103310000,1103550240000]
We don’t know if this function is monotone.
Because of =
that we can=20
calculate second derivative
d(2)f(x)=3D -50000 + 7000* x - 300* x*x + 4* x*x*x
Interval extension of this function is equal to:
d(2)f([-1000, 1]) =3D [-4307050000,4257000]
We don’t know if this function is monotone.
Because of =
that we can=20
calculate third derivative
d(3)f(x)=3D 7000 - 600* x + 12*x*x
Interval extension of this function is equal to:
d(3)f([-1000,1])=3D[-5600,12607000]
We don’t know if this function is monotone.
Because of =
that we can=20
calculate forth derivative
d(4)f(x)=3D -600+24*x
Interval extension of this function is equal to:
d(4)f([-1000,1]) =3D [-24600,-576]
We can see that the sign of the forth derivative is =
constant.
Because of=20
that third derivative is monotone and
extreme value of this function =
can be=20
calculated
using endpoints of given interval.
d(3)f(-1000) =3D 12607000
d(3)f(1) =3D 6412
We can see that the sign of the third derivative is =
constant.
Because of=20
that second derivative is monotone and
extreme value of this =
function can be=20
calculated
using endpoints of given interval.
d(2)f(-1000)=3D -4.3071e+009
d(2)f(1)=3D -43296
We can see that the sign of the second derivative is =
constant.
Because=20
of that first derivative is monotone and
extreme value of this =
function can=20
be calculated
using endpoints of given interval.
d(1)f(-1000) =3D 1.1036e+012
d(1)f(-1) =3D =
193401
We can see that the sign of the first derivative is =
constant.
Because of=20
that function f is monotone and
extreme value of this function can =
be=20
calculated
using endpoints of given interval.
f(-1000)=3D -2.2619e+014
f(1)=3D 2.1614e+005
Finally
f([-1000, 1])=3D[ -2.2619e+014, 2.1614e+005]
This is the exact range of the function f.
If this procedure fails,
we can divide the interval into =
two parts=20
and repeat procedure again.
If the boxes are sufficiently small =
then we=20
can apply Taylor model.
This procedure can be also applied in multidimensional case.
Pownuk A., New inclusion functions in interval global optimization =
of=20
engineering structures.
EUROPEAN CONFERENCE ON COMPUTATIONAL=20
MECHANICS,
Cracow, 26 - 29 June 2001, pp.460-461
Matlab code:
lowerX=3D-1000;
upperX=3D =
1;
x=3Dinterval(lowerX,upperX);
'First order derivative'
240000-50000*x+3500*=20
x*x-100*x*x*x+x*x*x*x
'Second order derivative'
-50000 + 7000* x - =
300*=20
x*x + 4* x*x*x
'Third order derivative'
7000 - 600* x + =
12*x*x
'Fourth=20
order derivative'
-600+24*x
x=3DlowerX;
y4_lower=3D-600+24*x
x=3DupperX;
y4_upper=3D-60=
0+24*x
x=3DlowerX;
y3_lower=3D7000 - 600* x + =
12*x*x
x=3DupperX;
y3_upper=3D7000=20
- 600* x + 12*x*x
x=3DlowerX;
y2_lower=3D-50000 + 7000* x - 300* x*x + 4*=20
x*x*x
x=3DupperX;
y2_upper=3D-50000 + 7000* x - 300* x*x + 4* =
x*x*x
x=3DlowerX;
y1_lower=3D240000-50000 *x+3500* x*x-100*=20
x*x*x+x*x*x*x
x=3DupperX;
y1_upper=3D240000-50000 *x+3500* =
x*x-100*=20
x*x*x+x*x*x*x
x=3DlowerX;
y0_lower=3D240000 * x - 25000 * x^2 + 3500 * x^3/3 - =
25*x^4 +=20
x^5/5
x=3DupperX;
y0_upper=3D240000 * x - 25000 * x^2 + 3500 * =
x^3/3 - 25*x^4=20
+ x^5/5
Regards,
Andrzej Pownuk
------=_NextPart_000_004D_01C1C52C.75D12C00--
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 6 12:48:25 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g26ImOp14395
for reliable_computing-outgoing; Wed, 6 Mar 2002 12:48:24 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g26ImGF14391
for ; Wed, 6 Mar 2002 12:48:17 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g26Im9qM058116;
Wed, 6 Mar 2002 19:48:10 +0100
Message-ID: <3C866469.6CF1FEB7 [at] univie [dot] ac.at>
Date: Wed, 06 Mar 2002 19:48:09 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: berz [at] msu [dot] edu
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models (repost)
References:
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Martin Berz wrote:
> One that we
> have been working on is the normal form defect problem from dynamical
> systems theory. [...] can be found in a recent paper in
> Nonlinear Analysis, http://bt.nscl.msu.edu/cgi-bin/display.pl?name=HOINL00
Could you please post a precise description of this and related problems
from applications, so that one can use them as test examples?
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 6 13:27:40 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g26JRdM14530
for reliable_computing-outgoing; Wed, 6 Mar 2002 13:27:39 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g26JRYF14526
for ; Wed, 6 Mar 2002 13:27:35 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g26JRSqM121538;
Wed, 6 Mar 2002 20:27:29 +0100
Message-ID: <3C866DA0.FAA1E6E3 [at] univie [dot] ac.at>
Date: Wed, 06 Mar 2002 20:27:28 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: berz [at] msu [dot] edu, reliable_computing [at] interval [dot] louisiana.edu
Subject: Taylor models - how to get valid comparisons
References: <3C866469.6CF1FEB7 [at] univie [dot] ac.at>
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Martin,
> Nonlinear Analysis, http://bt.nscl.msu.edu/cgi-bin/display.pl?name=HOINL00
I looked at the paper. I find it quite uninformative as regards the 6D
example. It is a bit strange to compare your method against simple
interval
evaluation, which is clear not to perform well. Any method can be made
to look very well if contrasted with the simplest of all methods. But
one would not compare a good optimization method against steepest
descent, or a good integrator against computing Riemann sums (which is
the analogue of interval evaluation) - so why do you do your comparisons
in such a useless way?
To see how your method compares with other state of the art techniques,
you'd have to compare it at least to techniques that use centered forms
with slopes which are available for easy use in Rump's INTLAB
(and perhaps to Bernstein polynomial techniques, and to affine
arithmetic),
and then it is likely that the huge improvement factors
claimed boil down to quite a small improvement. (Or a large one - then
it would be a fair victory!) Unfortunately, your other publications on
Taylor methods also suffer from similar presentation problems.
As to the reachable accuracy, I don't believe your claims that the
enclosure found is of high order; your results only show that the
remainder interval
can be enclosed to high order. But you still have to enclose the range
of the Taylor polynomial (with real coefficients) by an interval, and if
you
do it by using the Horner or the power form, you only get an accuracy of
O(h^2). Since you usually use such a simple evaluation scheme (at least
to
present your examples), your claims are just hot air, it seems.
I hope this will motivate to present a really convincing demonstration
of the
quality of your methods...
Best wishes,
Arnold
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 6 13:39:51 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g26JdpW14630
for reliable_computing-outgoing; Wed, 6 Mar 2002 13:39:51 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g26JdiF14625
for ; Wed, 6 Mar 2002 13:39:45 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g26JddqM157668;
Wed, 6 Mar 2002 20:39:40 +0100
Message-ID: <3C86707B.55475A90 [at] univie [dot] ac.at>
Date: Wed, 06 Mar 2002 20:39:39 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: berz [at] msu [dot] edu, reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
References: <3C866469.6CF1FEB7 [at] univie [dot] ac.at> <3C866DA0.FAA1E6E3 [at] univie [dot] ac.at>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Arnold Neumaier wrote:
> you'd have to compare it at least to techniques that use centered forms
> with slopes which are available for easy use in Rump's INTLAB
> (and perhaps to Bernstein polynomial techniques, and to affine
> arithmetic),
Another relevant comparison would be to a modified Moore-Skelboe
algorithm,
applied twice to get the lower and upper bound. This is a little
inefficient since part of the wirk is duplicated, but it has the
advantage that it can be done in a simple way since the NEOS server
allows one to solve global optimization problems on a box online
via the WWW. See
http://www-neos.mcs.anl.gov/neos/solvers/GO:GLOBMIN/
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 05:37:14 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28BbDB12292
for reliable_computing-outgoing; Fri, 8 Mar 2002 05:37:13 -0600 (CST)
Received: from mailhost.iitb.ac.in (garbo.iitb.ac.in [203.197.74.149] (may be forged))
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with SMTP id g28BaP312026
for ; Fri, 8 Mar 2002 05:37:04 -0600 (CST)
Received: (qmail 13129 invoked from network); 8 Mar 2002 11:12:59 -0000
Received: from mailscan2.iitb.ernet.in (HELO thisdomain) (144.16.108.202)
by mailhost.iitb.ac.in with SMTP; 8 Mar 2002 11:12:59 -0000
Received: from nataraj by iitb.ac.in ; Fri, 08 Mar 2002 17:06:08 +0530
Date: Fri, 08 Mar 2002 17:06:08 +0530
X-Originating-IP: 144.16.100.71
X-Auth-User: nataraj [at] ee [dot] iitb.ernet.in
From: "P. S. V. Nataraj"
To:
Subject: RE: Taylor models - how to get valid comparisons
Date: Fri, 8 Mar 2002 17:11:03 +0530
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="Windows-1252"
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
In-Reply-To: <3C86707B.55475A90 [at] univie [dot] ac.at>
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear All,
For a new inclusion function form having higher order convergence, along
with a convergence study of this form vs. that of Berz's Taylor model, pl.
see our paper (under review):
www.ee.iitb.ac.in/~nataraj/Super_TB_ps.zip
In the new form, Bernstein polynomial techniques were used to bound the
range of the Taylor polynomial part. We studied in this paper six problems,
of dimensions varying from 1 to 6.
The new form (along with Taylor model) has also been used in a modified
Moore-Skelboe Global Optimization algorithm in our paper (to appear in Jl.
Global Optimization)
www.ee.iitb.ac.in/~nataraj/GOTB_Final_PS.zip
In all our studies, we badly needed a good collection of challenge problems
to study the convergence behavior of the various forms.
Can somebody suggest a good collection of such problems - preferably with a
structure more general than polynomial, and dimensions varying from 1 to (at
least) 6 ?
Regards,
Nataraj
..............................................
Prof. P. S. V. Nataraj
Systems and Control Engineering Group
Department of Electrical Engineering
Indian Institute of Technology
Bombay 400 076 India
Ph: +91-022-5723757 Fax: +91-022-5726263
Email: nataraj [at] ee [dot] iitb.ernet.in
-----Original Message-----
From: owner-reliable_computing [at] interval [dot] louisiana.edu
[mailto:owner-reliable_computing [at] interval [dot] louisiana.edu]On Behalf Of
Arnold Neumaier
Sent: Thursday, March 07, 2002 1:12 AM
To: berz [at] msu [dot] edu; reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
Arnold Neumaier wrote:
> you'd have to compare it at least to techniques that use centered forms
> with slopes which are available for easy use in Rump's INTLAB
> (and perhaps to Bernstein polynomial techniques, and to affine
> arithmetic),
Another relevant comparison would be to a modified Moore-Skelboe
algorithm,
applied twice to get the lower and upper bound. This is a little
inefficient since part of the wirk is duplicated, but it has the
advantage that it can be done in a simple way since the NEOS server
allows one to solve global optimization problems on a box online
via the WWW. See
http://www-neos.mcs.anl.gov/neos/solvers/GO:GLOBMIN/
---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 09:46:18 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28FkIZ18782
for reliable_computing-outgoing; Fri, 8 Mar 2002 09:46:18 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28FkD318778
for ; Fri, 8 Mar 2002 09:46:13 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g28FjouS116070;
Fri, 8 Mar 2002 16:45:52 +0100
Message-ID: <3C88DCAE.9BD1F39D [at] univie [dot] ac.at>
Date: Fri, 08 Mar 2002 16:45:50 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: "P. S. V. Nataraj"
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
References:
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
"P. S. V. Nataraj" wrote:
> For a new inclusion function form having higher order convergence, along
> with a convergence study of this form vs. that of Berz's Taylor model,
> www.ee.iitb.ac.in/+AH4-nataraj/Super_TB_ps.zip
> www.ee.iitb.ac.in/+AH4-nataraj/GOTB_Final_PS.zip
Thanks for the papers. Very nice results! It confirms my suspicion that
the Taylor model only has the quadratic approximation property,
and it shows a way how to modify it to get truly high order
with good efficiency in low dimensions.
One correction:
You state that the Bernstein form gives exact results for sufficiently
small boxes. But this is true only if the extremal value is attained in
a box; it is not the case, e.g., for f(x)=x^3-6x in [0,2] since the
minimum
is irrational. Thus you need slight modifications in your GO algorithm:
you must use the computed upper bound for min p(x) instead of min p(x),
and probably you must also adjust your criterion for stopping Bernstein
subdivision. I'd also recommend that you mention the leading order of
the
cost of the transformation to Bernstein form, since this may explain the
limitations of your method in higher dimensions.
> In all our studies, we badly needed a good collection of challenge problems
> to study the convergence behavior of the various forms.
>
> Can somebody suggest a good collection of such problems - preferably with a
> structure more general than polynomial, and dimensions varying from 1 to (at
> least) 6 ?
http://www.mat.univie.ac.at/+AH4-neum/glopt/test.html
contains collections of test problems for global optimization.
Both the Dixon-Szego test set and the More test set with bounds by Gay
are low-dimiensional (up to dimension 12, but some have varying
dimensions).
Instead of global optimization, you can also find the ranges,
and shrink the domains to see how the size of the box
affects the overestimation of the range.
You can generate arbitrarily challenging test problems with the
rational test problem generator described in
http://www.mat.univie.ac.at/+AH4-neum/papers.html#ratglob
Best wishes,
Arnold
PS. Do you have a WWW page woth your publications?
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 10:41:45 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28GfjF19024
for reliable_computing-outgoing; Fri, 8 Mar 2002 10:41:45 -0600 (CST)
Received: from mail.epost.de ([64.39.38.76])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28GfZ319020
for ; Fri, 8 Mar 2002 10:41:35 -0600 (CST)
Received: from TP570Berz (12.245.210.11) by mail.epost.de (5.5.052) (authenticated as martin.berz [at] epost [dot] de)
id 3C6B20EC00478282; Fri, 8 Mar 2002 17:41:05 +0100
Reply-To:
From: "Martin Berz"
To: "Arnold Neumaier" ,
Subject: RE: Taylor models - how to get valid comparisons
Date: Fri, 8 Mar 2002 11:41:02 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
Importance: Normal
In-Reply-To: <3C866DA0.FAA1E6E3 [at] univie [dot] ac.at>
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g28Gff319021
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear Arnold et al.,
+AD4-
+AD4- +AD4- Nonlinear Analysis,
+AD4- http://bt.nscl.msu.edu/cgi-bin/display.pl?name+AD0-HOINL00
+AD4-
+AD4- I looked at the paper. I find it quite uninformative as regards the 6D
+AD4- example.
Well, the 6D example cannot be described as nicely and compactly as the Gritton problem also studied in the paper, which is merely a one variable high-order polynomial that can be written down analytically. As is described, the 6D example is +ACI-industrial strength+ACI-, a composition of three polynomials of order 10 in six variables. That makes it impossible to list in detail, since each of these polynomials has many thousands of coefficients. However, we are happy to provide you or anyone else who asks the set of coefficients to try whatever method they want on it, which would certainly be interesting. From the past we also have tools in FORTRAN, COSY language, C or C+-+- that we can dig out that evaluates the polynomials.
The theory behind how these polynomials are obtained and why they are important can for example be found in a recent book of mine, Modern Map Methods in Particle Beam Physics, Academic Press, 1999, ISBN 0-12-014750-5, posted at http://bt.nscl.msu.edu/cgi-bin/display.pl?name+AD0-AIEP108book . The relevant part is the theory of +ACI-normal forms+ACI- in Chapter 7. However, as with perhaps many other heavy duty problems from other fields, you have to be prepared to invest a fair amount of time to get to the bottom of the theory.
+AD4- It is a bit strange to compare your method against simple
+AD4- interval
+AD4- evaluation, which is clear not to perform well. Any method can be made
+AD4- to look very well if contrasted with the simplest of all methods. But
+AD4- one would not compare a good optimization method against steepest
+AD4- descent, or a good integrator against computing Riemann sums (which is
+AD4- the analogue of interval evaluation) - so why do you do your comparisons
+AD4- in such a useless way?
+AD4-
+AD4- To see how your method compares with other state of the art techniques,
+AD4- you'd have to compare it at least to techniques that use centered forms
+AD4- with slopes which are available for easy use in Rump's INTLAB
+AD4- (and perhaps to Bernstein polynomial techniques, and to affine
+AD4- arithmetic),
+AD4- and then it is likely that the huge improvement factors
+AD4- claimed boil down to quite a small improvement. (Or a large one - then
+AD4- it would be a fair victory+ACE-) Unfortunately, your other publications on
+AD4- Taylor methods also suffer from similar presentation problems.
Well, first of all the paper you are looking at has a strict page limit, and we had to throw away nearly half of what we wanted in there already+ADs- and then it is in a field outside of traditional interval methods, where using many different methods you introduce may make you loose more of the audience. We did, however, make several comparisons in the direction you mention. First, we evaluated the system with linear Taylor models which have quadratic convergence and linear cancellation of dependencies. Hence except for the cancellation, they provide similar behavior to centered forms and to affine arithmetic (see also Baker's comments from a few days ago - by the way, Baker, did you study your system with higher order Taylor models as well?). The resulting second order method certainly helps somewhat compared to the intervals, but is still far from sufficient to crack this problem. I suppose when Kyoko is back from her meeting, she may possibly be able to dig out some detailed numbers and provide them.
Regarding the question of optimization, we tried several of the packages including Rump's and some earlier(?) version of Globsol, but they were all limited by the size of the buffer because no intervals could be excluded due to overestimation. I guess these tools have some of the state of the art methods you mention built in to the extent they have proven useful. If you know how to do it with NEOS, in particular how to make the interface to evaluate the function in this complicated case, I think this would be very worthwhile to pursue.
+AD4-
+AD4- As to the reachable accuracy, I don't believe your claims that the
+AD4- enclosure found is of high order+ADs- your results only show that the
+AD4- remainder interval
+AD4- can be enclosed to high order. But you still have to enclose the range
+AD4- of the Taylor polynomial (with real coefficients) by an interval, and if
+AD4- you
+AD4- do it by using the Horner or the power form, you only get an accuracy of
+AD4- O(h+AF4-2). Since you usually use such a simple evaluation scheme (at least
+AD4- to
+AD4- present your examples), your claims are just hot air, it seems.
Well, may I propose to try to keep the air cool by not hyperventilating? First, so far we usually don't even get to the point of explaining sophisticated polynomial bounding because just getting across the basic Taylor model idea takes all the time. And again, in most cases the enclosure of the polynomial turns out to offer not so much additional gain for the overall accuracy, once you add the minimum level of sophistication of using an intrinsic square operation for even orders. Some representative examples of this are given, for example, in Makino's dissertation http://bt.nscl.msu.edu/cgi-bin/display.pl?name+AD0-makinophd p. 119-123. Keep in mind too that you never have to range bound any intermediate results, you leave them in the Taylor model form. That's one of the tricks that helps so much in the verified integrators.
However, there are various extensions of this range bounding question+ADs- for example we know how to range bound general quadratic forms and in case of univariate Taylor models, since we know how to get zeros from polynomials of up to fourth order up to arithmetic order, we can rigorously bound a polynomial up to fifth order. In any case, what's left to bound is some kind of higher order part+ADs- and even if you use just plain intervals for that, the overestimation of the true range is usually in the range of a few percent only. And since you do this only once at the very end but never in intermediate steps, this is your total overestimation.
However, if you REALLY want to, and for the sake of the theoretical argument, you CAN ALSO BOUND THE POLYNOMIAL of the Taylor model with an overestimation that truly scales with order (n+-1) like the remainder. Of course this comes with the standard caveat that you have to stay sufficiently away from the floor due to machine precision, and it ONLY works for Taylor polynomials where the contributions of the higher orders fall off quickly, which however is what we have in Taylor models. There are at least two methods that we know that allow you to do that. The first method is outlined in Makino's dissertation p. 128-130, it is iterative and in practical cases can reduce the polynomial overestimation below the remainder bound. It is based on the fact that the linear part locally dominates, which when combined with a crude estimate of all nonlinear contributions, provides a way to narrow down the regions where maxima can occur.
+AD4-
+AD4- I hope this will motivate to present a really convincing demonstration
+AD4- of the quality of your methods...
+AD4-
+AD4- Best wishes,
+AD4-
+AD4- Arnold
+AD4-
Sure, we are always motivated +ADs--) To this end, we'd be more than happy to work with anybody who wants to try his/her favorite tool on the normal form defect problem and see what happens.
Best wishes,
Martin
P.S.: While I was typing this, I saw the posting of Nataraj+ADs- however, I couldn't open the .ps files, Ghostview 4 stopped somewhere early on in both papers and I couldn't print them either - can others open them? Can Nataraj perhaps post a pdf?
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 11:09:39 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28H9c519148
for reliable_computing-outgoing; Fri, 8 Mar 2002 11:09:38 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28H9I319144
for ; Fri, 8 Mar 2002 11:09:19 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g28H9AE16519;
Fri, 8 Mar 2002 12:09:10 -0500 (EST)
Message-ID: <000e01c1c6c3$90d9cdc0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore"
To:
Cc: "interval"
References: +ADw-LOBBLFLDLCOABDBDAMICAEJFEBAA.berz+AEA-msu.edu+AD4-
Subject: Re: Taylor models - how to get valid comparisons
Date: Fri, 8 Mar 2002 12:06:18 -0500
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
+AD4- P.S.: While I was typing this, I saw the posting of Nataraj+ADs- however, I
couldn't open the .ps files, Ghostview 4 stopped somewhere early on in both
papers and I couldn't print them either - can others open them? Can Nataraj
perhaps post a pdf?
+AD4-
I had the same problem, and I have the same request.
Ramon Moore
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 11:28:12 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28HSC819272
for reliable_computing-outgoing; Fri, 8 Mar 2002 11:28:12 -0600 (CST)
Received: from mailgate.rz.uni-karlsruhe.de (mailgate.rz.uni-karlsruhe.de [129.13.64.97])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28HS6319268
for ; Fri, 8 Mar 2002 11:28:07 -0600 (CST)
Received: from there (rz37@rzm-lohner.rz.uni-karlsruhe.de [172.21.99.37])
by mailgate.rz.uni-karlsruhe.de with smtp (Exim 3.33 #1)
id 16jO9k-0006PK-00; Fri, 08 Mar 2002 18:27:48 +0100
Content-Type: text/plain;
charset="iso-8859-1"
From: Rudolf Lohner
Reply-To: Rudolf.Lohner [at] rz [dot] uni-karlsruhe.de
Organization: Universitaet Karlsruhe (TH), Rechenzentrum
To:
Subject: RE: Taylor models - how to get valid comparisons
Date: Fri, 8 Mar 2002 18:27:47 +0100
X-Mailer: KMail [version 1.3.2]
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Message-Id:
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Edit the .ps files in your favorite text editor and remove the printer
job control commands.
The files should start with the line
%!PS-Adobe-3.0
and end with the line
%%EOF
Remove everything before and after. Then you should be able to open the
files with gv and print them.
Rudolf
> +AD4- P.S.: While I was typing this, I saw the posting of Nataraj+ADs-
> however, I
> couldn't open the .ps files, Ghostview 4 stopped somewhere early on in both
> papers and I couldn't print them either - can others open them? Can Nataraj
> perhaps post a pdf?
> +AD4-
>
> I had the same problem, and I have the same request.
--
Rudolf Lohner --- Universitaet Karlsruhe (TH) --- Rechenzentrum
Zirkel 2, D-76128 Karlsruhe, phone/fax: +49 721 {608-6958 | 32550}
www: http://www.uni-karlsruhe.de/~Rudolf.Lohner
email: Rudolf.Lohner [at] rz [dot] uni-karlsruhe.de
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 11:40:31 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28HeVo19368
for reliable_computing-outgoing; Fri, 8 Mar 2002 11:40:31 -0600 (CST)
Received: from mail.epost.de ([64.39.38.76])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28HeP319364
for ; Fri, 8 Mar 2002 11:40:25 -0600 (CST)
Received: from TP570Berz (12.245.210.11) by mail.epost.de (5.5.052) (authenticated as martin.berz [at] epost [dot] de)
id 3C6B20EC0047B9B2; Fri, 8 Mar 2002 18:39:56 +0100
Reply-To:
From: "Martin Berz"
To: "Arnold Neumaier" ,
"P. S. V. Nataraj"
Cc:
Subject: RE: Taylor models - how to get valid comparisons
Date: Fri, 8 Mar 2002 12:39:50 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
Importance: Normal
In-Reply-To: <3C88DCAE.9BD1F39D [at] univie [dot] ac.at>
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g28HeR319365
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Follow up to my previous message, which was written before receiving this one... the speed and efficiency of the internet keeps you on your toes+ACE- From what Arnold says, it seems these papers contain another way of bounding the polynomial part that shows that higher order accuracies are possible not only for the remainder bound, but even for the polyomial part. That confirms my statement, and good to hear that independently. However, the statement
+AD4- the Taylor model only has the quadratic approximation property,
in my opinion is not quite right. It should read something like:
+ACI-The Taylor model method provides an asymptotic accuracy equal to min(n+-1,p), where n is the order of the Taylor polynomial, and p the order of the scheme used for bounding the Taylor polynomial. If mere interval evaluation of the polynomial is used, then p+AD0-2, as for all naive interval bounding. But various more efficient polynomial bounding schemes exist with p higher than 2 exist. +ACI-
I hope we can agree on this, ok?
Regarding the collection of optimization examples that Arnold mentions, and similar such things by Baker, George, and others: would it make sense or of interest to provide a FORTRAN code for our nasty invariant defect function?
Martin
+AD4- -----Original Message-----
+AD4- From: owner-reliable+AF8-computing+AEA-interval.louisiana.edu
+AD4- +AFs-mailto:owner-reliable+AF8-computing+AEA-interval.louisiana.edu+AF0-On Behalf Of
+AD4- Arnold Neumaier
+AD4- Sent: Friday, March 08, 2002 10:46 AM
+AD4- To: P. S. V. Nataraj
+AD4- Cc: reliable+AF8-computing+AEA-interval.louisiana.edu
+AD4- Subject: Re: Taylor models - how to get valid comparisons
+AD4-
+AD4-
+AD4- +ACI-P. S. V. Nataraj+ACI- wrote:
+AD4-
+AD4- +AD4- For a new inclusion function form having higher order convergence, along
+AD4- +AD4- with a convergence study of this form vs. that of Berz's Taylor model,
+AD4- +AD4- www.ee.iitb.ac.in/+AH4-nataraj/Super+AF8-TB+AF8-ps.zip
+AD4- +AD4- www.ee.iitb.ac.in/+AH4-nataraj/GOTB+AF8-Final+AF8-PS.zip
+AD4-
+AD4- Thanks for the papers. Very nice results+ACE- It confirms my suspicion that
+AD4- the Taylor model only has the quadratic approximation property,
+AD4- and it shows a way how to modify it to get truly high order
+AD4- with good efficiency in low dimensions.
+AD4-
+AD4- One correction:
+AD4- You state that the Bernstein form gives exact results for sufficiently
+AD4- small boxes. But this is true only if the extremal value is attained in
+AD4- a box+ADs- it is not the case, e.g., for f(x)+AD0-x+AF4-3-6x in +AFs-0,2+AF0- since the
+AD4- minimum
+AD4- is irrational. Thus you need slight modifications in your GO algorithm:
+AD4- you must use the computed upper bound for min p(x) instead of min p(x),
+AD4- and probably you must also adjust your criterion for stopping Bernstein
+AD4- subdivision. I'd also recommend that you mention the leading order of
+AD4- the
+AD4- cost of the transformation to Bernstein form, since this may explain the
+AD4- limitations of your method in higher dimensions.
+AD4-
+AD4- +AD4- In all our studies, we badly needed a good collection of
+AD4- challenge problems
+AD4- +AD4- to study the convergence behavior of the various forms.
+AD4- +AD4-
+AD4- +AD4- Can somebody suggest a good collection of such problems -
+AD4- preferably with a
+AD4- +AD4- structure more general than polynomial, and dimensions varying
+AD4- from 1 to (at
+AD4- +AD4- least) 6 ?
+AD4-
+AD4- http://www.mat.univie.ac.at/+AH4-neum/glopt/test.html
+AD4- contains collections of test problems for global optimization.
+AD4- Both the Dixon-Szego test set and the More test set with bounds by Gay
+AD4- are low-dimiensional (up to dimension 12, but some have varying
+AD4- dimensions).
+AD4- Instead of global optimization, you can also find the ranges,
+AD4- and shrink the domains to see how the size of the box
+AD4- affects the overestimation of the range.
+AD4-
+AD4- You can generate arbitrarily challenging test problems with the
+AD4- rational test problem generator described in
+AD4- http://www.mat.univie.ac.at/+AH4-neum/papers.html+ACM-ratglob
+AD4-
+AD4- Best wishes,
+AD4-
+AD4- Arnold
+AD4-
+AD4- PS. Do you have a WWW page woth your publications?
+AD4-
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 8 12:11:07 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g28IB7519497
for reliable_computing-outgoing; Fri, 8 Mar 2002 12:11:07 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g28IB1319493
for ; Fri, 8 Mar 2002 12:11:02 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g28IAs0E076068;
Fri, 8 Mar 2002 19:10:55 +0100
Message-ID: <3C88FEAE.2336F990 [at] univie [dot] ac.at>
Date: Fri, 08 Mar 2002 19:10:54 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: berz [at] msu [dot] edu, reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
References:
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Martin Berz wrote:
> the 6D example is "industrial strength", a composition of three
polynomials of order 10 in six variables. That makes it impossible
to list in detail, since each of these polynomials has many thousands
of coefficients. However, we are happy to provide you or anyone else
who asks the set of coefficients to try whatever method they want on it,
which would certainly be interesting.
I'd be happy with a problem description in machine readable form.
There is no need to have the polynomials represented in power form;
any form that produces the right function values is ok.
AMPL input would be most desirable for our group in Vienna,
but a Fortran or C program that defines the polynomials as a sequence
of simple assignments, with loops allowed, would be ok, too.
Providing this on your web site would make the problem accessible
to everyone.
> we evaluated the system with linear Taylor models which [...] is still
> far from sufficient to crack this problem. I suppose when Kyoko is back
> from her meeting, she may possibly be able to dig out some detailed
> numbers and provide them.
Yes, please!
> If you know how to do it with NEOS, in particular how to make the
> interface to evaluate the function in this complicated case,
> I think this would be very worthwhile to pursue.
The page on the NEOS server I quoted gives the instructions; namely,
essentially provide f95 evaluation routines for f and df.
But maybe it GLOBMIN also suffers from digestion. In any case, reporting
such information is important to gauge the quality of a new approach.
> so far we usually don't even get to the point of explaining
> sophisticated polynomial bounding because just getting across
> the basic Taylor model idea takes all the time.
But the basic model gets across in *one* publication, and then the
others should go into more detail! And the dissertation by Makino has
*no* sophisticated polynomial bounding apart from Horner; nothing to
suggest that the overestimation can be kept at high order.
> And again, in most cases the enclosure of the polynomial turns out to offer > not so much additional gain for the overall accuracy, once you add
> the minimum level of sophistication of using an intrinsic square operation
> for even orders. Some representative examples of this are given,
> for example, in Makino's dissertation
> http://bt.nscl.msu.edu/cgi-bin/display.pl?name=makinophd p. 119-123.
But this means that you are stuck with O(h^2) accuracy in dimension > 1,
against what you claimed. Since you nowhere compute the exact range,
one cannot see the overestimation in your tables.
> Keep in mind too that you never have to range bound any
> intermediate results, you leave them in the Taylor model form.
> That's one of the tricks that helps so much in the verified integrators.
This is what Hansen does in his recent Computing paper, but only with
quadratic term. It is what I guess is the *only* trick that makes
the Taylor model form in the form you propose useful,
but I found this nowhere spelled out as such.
> we know how to range bound general quadratic forms
How? I do not know any efficient way of bounding quadratic forms
to higher than O(h^2) accuracy, except through subdivision algorithms.
> in case of univariate Taylor models
This is known; I agree.
> what's left to bound is some kind of higher order part;
> and even if you use just plain intervals for that,
> the overestimation of the true range is usually in the range of
> a few percent only.
I agree here; but this sounds quite different from your high order
claims
- it does not go down to a few millionth if you increase the order!
> However, if you REALLY want to, and for the sake of the theoretical
> argument, you CAN ALSO BOUND THE POLYNOMIAL of the Taylor model with
> an overestimation that truly scales with order (n+-1) like the remainder.
You say it now, but never in your publications, that this needs
additional techniques (and you don't provide these techniques!).
What you wrote in print always sounded like your method solved these
problems already, and the interested reader (and more readers than you
think are sophisticated enough that they don't need to get the same
starter
every time, and don't notice that they are never served the real meat)
is left to wonder what precisely is the degree of reliability of your
statements. (It is better to claim less than to raise expectations
that cannot be satisfied. In the past, the image of interval methods
suffered severely from initial overenthusiasm that turned interested
people away, or even hostile, when they noticed that the claims
were not substantiated.)
> it ONLY works for Taylor polynomials where the contributions of the
> higher orders fall off quickly, which however is what we have in
> Taylor models.
Only for high order terms! Nothing guarantees that for a general
function, the quadratic contribution is already small. If I give you
a homogeneous quadratic form in 6 variables to be enclosed in
[-0.05,0.05],
the Taylor form of order n=5 is the original function, and I want to see
your method that provides an overestimation that truly scales with order
n+-1.
> The first method is outlined in Makino's dissertation p. 128-130,
but only in the univariate case, where Cornelius and Lohner solved
the problem already in 1984. The case important for most applications is
that of dimensions 2-6 (or even higher).
> Sure, we are always motivated ;-)
> To this end, we'd be more than happy to work with anybody
> who wants to try his/her favorite tool on the normal form
> defect problem and see what happens.
But this requires that you put the analytic form of sample
examples on the Web.
I'll have a look at the application in your book...
> I couldn't open the .ps files, Ghostview 4 stopped somewhere early on
> in both papers and I couldn't print them either - can others open them?
> Can Nataraj perhaps post a pdf?
On my system there is ps2pdf, and it translates both papers to pdf,
which can be printed with acroread.
> "The Taylor model method provides an asymptotic accuracy equal to
> min(n+-1,p), where n is the order of the Taylor polynomial,
> and p the order of the scheme used for bounding the Taylor polynomial.
> If mere interval evaluation of the polynomial is used, then p=2,
> as for all naive interval bounding. But various more efficient
> polynomial bounding schemes exist with p higher than 2 exist. "
In this form, your statement is correct. But my earlier statement,
> the Taylor model only has the quadratic approximation property,
was correct, too, for any of the versions of the Taylor model you
presented (for dimension >1) in any of your publications,
including Makino's thesis.
Nataraj's achievement consists in making the Taylor model truly of
higher order.
> Regarding the collection of optimization examples that
> Arnold mentions, and similar such things by Baker, George,
> and others: would it make sense or of interest to provide
> a FORTRAN code for our nasty invariant defect function?
Yes, very much!
Best wishes,
Arnold
From owner-reliable_computing [at] interval [dot] louisiana.edu Sat Mar 9 01:25:15 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g297PFs20872
for reliable_computing-outgoing; Sat, 9 Mar 2002 01:25:15 -0600 (CST)
Received: from mailhost.iitb.ac.in (garbo.iitb.ac.in [203.197.74.149] (may be forged))
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with SMTP id g297P6320868
for ; Sat, 9 Mar 2002 01:25:07 -0600 (CST)
Received: (qmail 13610 invoked from network); 9 Mar 2002 07:01:46 -0000
Received: from mailscan1.iitb.ac.in (HELO thisdomain) (144.16.108.201)
by mailhost.iitb.ac.in with SMTP; 9 Mar 2002 07:01:46 -0000
Received: from nataraj by iitb.ac.in ; Sat, 09 Mar 2002 12:55:01 +0530
Date: Sat, 09 Mar 2002 12:55:01 +0530
X-Originating-IP: 144.16.100.71
X-Auth-User: nataraj [at] ee [dot] iitb.ernet.in
From: "P. S. V. Nataraj"
To: "interval"
Cc: "Ramon Moore" ,
Subject: PDF files of Super-conv form and Taylor model papers
Date: Sat, 9 Mar 2002 12:59:51 +0530
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
In-Reply-To: <000e01c1c6c3$90d9cdc0$66ae1841 [at] columbus [dot] rr.com>
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g297P8320869
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Hi,
I am sorry for the trouble you have had with my zipped postscript files. I have made a PDF version of these files:
www.ee.iitb.ac.in/+AH4-nataraj/GOTB+AF8-Final+AF8-PDF.zip
www.ee.iitb.ac.in/+AH4-nataraj/Super+AF8-TB+AF8-PDF.zip
(Sorry, I do not have a WWW page).
Regards,
Nataraj
..............................................
Prof. P. S. V. Nataraj
Systems and Control Engineering Group
Department of Electrical Engineering
Indian Institute of Technology
Bombay 400 076 India
Ph: +-91-022-5723757 Fax: +-91-022-5726263
Email: nataraj+AEA-ee.iitb.ernet.in
-----Original Message-----
From: owner-reliable+AF8-computing+AEA-interval.louisiana.edu
+AFs-mailto:owner-reliable+AF8-computing+AEA-interval.louisiana.edu+AF0-On Behalf Of
Ramon Moore
Sent: Friday, March 08, 2002 10:44 PM
To: berz+AEA-msu.edu
Cc: interval
Subject: Re: Taylor models - how to get valid comparisons
+AD4- P.S.: While I was typing this, I saw the posting of Nataraj+ADs- however, I
couldn't open the .ps files, Ghostview 4 stopped somewhere early on in both
papers and I couldn't print them either - can others open them? Can Nataraj
perhaps post a pdf?
+AD4-
I had the same problem, and I have the same request.
Ramon Moore
---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Mar 11 01:33:44 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2B7Xhc04565
for reliable_computing-outgoing; Mon, 11 Mar 2002 01:33:43 -0600 (CST)
Received: from mailhost.iitb.ac.in (garbo.iitb.ac.in [203.197.74.149] (may be forged))
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with SMTP id g2B7XZ304560
for ; Mon, 11 Mar 2002 01:33:36 -0600 (CST)
Received: (qmail 6004 invoked from network); 11 Mar 2002 07:10:22 -0000
Received: from mailscan1.iitb.ac.in (HELO thisdomain) (144.16.108.201)
by mailhost.iitb.ac.in with SMTP; 11 Mar 2002 07:10:22 -0000
Received: from nataraj by iitb.ac.in ; Mon, 11 Mar 2002 13:03:34 +0530
Date: Mon, 11 Mar 2002 13:03:34 +0530
X-Originating-IP: 144.16.100.71
X-Auth-User: nataraj [at] ee [dot] iitb.ernet.in
From: "P. S. V. Nataraj"
To: "Arnold Neumaier"
Cc:
Subject: RE: Taylor models - how to get valid comparisons
Date: Mon, 11 Mar 2002 13:08:56 +0530
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
In-Reply-To: <3C88DCAE.9BD1F39D [at] univie [dot] ac.at>
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g2B7Xc304562
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Prof. Neumaier,
Thank you very much for your kind comments on our papers and the correction. Sorry, I do not have a WWW page.
We will investigate the performance of the various forms on the collections of test problems you suggested.
Regards,
Nataraj
..............................................
Prof. P. S. V. Nataraj
Systems and Control Engineering Group
Department of Electrical Engineering
Indian Institute of Technology
Bombay 400 076 India
Ph: +-91-022-5723757 Fax: +-91-022-5726263
Email: nataraj+AEA-ee.iitb.ernet.in
-----Original Message-----
From: neum+AEA-mailbox.univie.ac.at +AFs-mailto:neum+AEA-mailbox.univie.ac.at+AF0-On
Behalf Of Arnold Neumaier
Sent: Friday, March 08, 2002 9:16 PM
To: P. S. V. Nataraj
Cc: reliable+AF8-computing+AEA-interval.louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
+ACI-P. S. V. Nataraj+ACI- wrote:
+AD4- For a new inclusion function form having higher order convergence, along
+AD4- with a convergence study of this form vs. that of Berz's Taylor model,
+AD4- www.ee.iitb.ac.in/+AH4-nataraj/Super+AF8-TB+AF8-ps.zip
+AD4- www.ee.iitb.ac.in/+AH4-nataraj/GOTB+AF8-Final+AF8-PS.zip
Thanks for the papers. Very nice results+ACE- It confirms my suspicion that
the Taylor model only has the quadratic approximation property,
and it shows a way how to modify it to get truly high order
with good efficiency in low dimensions.
One correction:
You state that the Bernstein form gives exact results for sufficiently
small boxes. But this is true only if the extremal value is attained in
a box+ADs- it is not the case, e.g., for f(x)+AD0-x+AF4-3-6x in +AFs-0,2+AF0- since the
minimum
is irrational. Thus you need slight modifications in your GO algorithm:
you must use the computed upper bound for min p(x) instead of min p(x),
and probably you must also adjust your criterion for stopping Bernstein
subdivision. I'd also recommend that you mention the leading order of
the
cost of the transformation to Bernstein form, since this may explain the
limitations of your method in higher dimensions.
+AD4- In all our studies, we badly needed a good collection of challenge problems
+AD4- to study the convergence behavior of the various forms.
+AD4-
+AD4- Can somebody suggest a good collection of such problems - preferably with a
+AD4- structure more general than polynomial, and dimensions varying from 1 to (at
+AD4- least) 6 ?
http://www.mat.univie.ac.at/+AH4-neum/glopt/test.html
contains collections of test problems for global optimization.
Both the Dixon-Szego test set and the More test set with bounds by Gay
are low-dimiensional (up to dimension 12, but some have varying
dimensions).
Instead of global optimization, you can also find the ranges,
and shrink the domains to see how the size of the box
affects the overestimation of the range.
You can generate arbitrarily challenging test problems with the
rational test problem generator described in
http://www.mat.univie.ac.at/+AH4-neum/papers.html+ACM-ratglob
Best wishes,
Arnold
PS. Do you have a WWW page woth your publications?
---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Mar 12 22:59:28 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2D4xRB09607
for reliable_computing-outgoing; Tue, 12 Mar 2002 22:59:27 -0600 (CST)
Received: from mail.epost.de ([64.39.38.70])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2D4x6309603
for ; Tue, 12 Mar 2002 22:59:10 -0600 (CST)
Received: from TP570Berz (12.245.210.11) by mail.epost.de (5.5.052) (authenticated as martin.berz [at] epost [dot] de)
id 3C6B1E3900087A38 for reliable_computing [at] interval [dot] louisiana.edu; Wed, 13 Mar 2002 05:58:29 +0100
Reply-To:
From: "Martin Berz"
To: "Reliable+AF8-Computing+AEA-Interval. Louisiana. Edu"
Subject: FW: Taylor models - how to get valid comparisons
Date: Tue, 12 Mar 2002 23:58:44 -0500
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g2D4xL309604
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Hm, I sent this message yesterday, but I am not sure it worked ... it went to reliable+AF8-computing+AEA-interval.usl.edu, but it seems the right address now is reliable+AF8-computing+AEA-interval.louisiana.edu. So here it is again. Best, Martin
-----Original Message-----
From: Martin Berz +AFs-mailto:berz+AEA-msu.edu+AF0-
Sent: Monday, March 11, 2002 5:50 PM
To: Arnold Neumaier+ADs- Reliable Computing
Subject: RE: Taylor models - how to get valid comparisons
Dear Arnold et al.,
well, first of all it looks like there is still some hot air, and I propose to try to cool this down as carefully as we can+ADs- if we can do this, I believe it will help towards really effective communication and limit unsubstantiated claims. Also, along these lines, at the end of this message I will propose a few simple computations that we can do with various methods to check their performance, and encourage others to propose more of them. These examples will also help prevent just talking in vacuo, or more importantly, prevent from spreading ideas that aren't really true. I hope everybody can be agreeable to that.
+AD4-
+AD4- I'd be happy with a problem description in machine readable form.
+AD4-
Ok, we will do that.
+AD4- +AD4- we evaluated the system with linear Taylor models which +AFs-...+AF0- is still
+AD4- +AD4- far from sufficient to crack this problem. I suppose when Kyoko is back
+AD4- +AD4- from her meeting, she may possibly be able to dig out some detailed
+AD4- +AD4- numbers and provide them.
+AD4-
+AD4- Yes, please+ACE-
Ok, we will do that too.
+AD4-
+AD4- +AD4- If you know how to do it with NEOS, in particular how to make the
+AD4- +AD4- interface to evaluate the function in this complicated case,
+AD4- +AD4- I think this would be very worthwhile to pursue.
+AD4-
+AD4- The page on the NEOS server I quoted gives the instructions+ADs- namely,
+AD4- essentially provide f95 evaluation routines for f and df.
+AD4- But maybe it GLOBMIN also suffers from digestion. In any case, reporting
+AD4- such information is important to gauge the quality of a new approach.
+AD4-
>From the limited information I have about NEOS and a few discussions I had with Jorge More about this problem, I believe that NEOS has the digestion problem too, unless dramatic things have happened in the last two or so years that I don't know about yet.
+AD4- +AD4- so far we usually don't even get to the point of explaining
+AD4- +AD4- sophisticated polynomial bounding because just getting across
+AD4- +AD4- the basic Taylor model idea takes all the time.
+AD4-
+AD4- But the basic model gets across in +ACo-one+ACo- publication,
Well, to the really careful reader, yes. Yet we are still frequently and repeatedly being asked many of the basic questions, like +ACI-how and to what extent does it control dependency+ACI-, +ACI-why does the sharpness of the remainder bound decrease with order (n+-1)+ACI-, +ACI-why are higher orders beyond say two useful at all+ACI-. All these are important but perhaps not completely universally clear+ADs- to anybody to whom they are clear, I apologize. Actually one of the questions that is still borderline basic, yet very important here, is +ACI-what role does the sophistication of the polynomial bounding play+ACI-.
+AD4- and then the others should go into more detail+ACE-
For those to whom these points are clear, we have written some advanced papers on details about the dependency problem, quadrature, ODE integration, DAEs, near earth asteroids, stability theory, verified inversion, etc. Most of these, except when asked for by referees etc, don't include the basic theory again. In most of these applications, the range bounding question is not important because either 1) values at the endpoints are plugged in (quadrature or ODE integration), or 2) the problem is dominated by a complicated functional dependency situation (ODE integration, stability theory etc). For those topics that are relevant that we haven't yet addressed, sorry, we are humans, and there is life outside intervals too ...
Altogether, from what we see so far, the strength of the Taylor models lies in these listed areas+ADs- and as a general rule, one should keep all operations in Taylor model format from beginning to end, without intermediate representation via intervals, i.e. not do intermediate range bounding. For plain range bounding itself, Taylor models may be useful if other methods fail because of the dependency problem+ADs- this is addressed to the extent it fits into the page limit in the paper we were talking about last time. In this case, and almost only there, does the question of how to compute the range of the polynomial of the Taylor model matter. But even there, for practical problems the question is not necessarily to squeeze out the last bit of sharpness. If you want to do that, however, you need high order range bounding of the polynomial.
+AD4- And the dissertation by Makino has
+AD4- +ACo-no+ACo- sophisticated polynomial bounding apart from Horner+ADs- nothing to
+AD4- suggest that the overestimation can be kept at high order.
+AD4-
I don't agree (besides the above point that it's often not needed). Kyoko's dissertation contains the method of the linear dominated bounder which under the assumption of regularity of the linear part (and mild limitations on the floating point error) can get an inclusion with a sharpness that is aymptocially of the size of the remainder bound, order (n+-1), and which works in high dimensions, is robust and fast. (Additionally, should the linear part not be regular, the method usually reduces the dimensionality of the problem by the rank of the linear part, and then you can attack it perhaps with other means.) Whether or not this is +ACI-sophisticated+ACI- lies in the eye of the beholder, but it gets the job done in almost all cases. (In fact in her diss. she illustrates it only in one variable and for bounds of order three, but it is clear how this generalizes - should this not be the case, I'd be happy to say more next time, but in any case what she wrote should +ACI-suggest+ACI- that this is possible). In addition, she also describes a multivariate quadratic form bounder which allows to get a third order inclusion under rather mild conditions, but it doesn't scale so favorably to higher dimensions+ADs- and there is the one dimensional fifth order bounder.
+AD4-
+AD4- But this means that you are stuck with O(h+AF4-2) accuracy in dimension +AD4- 1,
+AD4- against what you claimed.
we are not stuck with the range bounders mentioned above. But nevertheless, let's still look at this in more detail. In a case where you really would want to use Taylor models, i.e. big overestimation, if it works you win because Taylor models can to some extent control dependencies. This effect is much more important than the ability to range bound most efficiently.
+AD4- Since you nowhere compute the exact range, one cannot see the overestimation in your tables.
+AD4-
Well, if we knew the exact range, we wouldn't need intervals +ADs--) But besides this ironic comment, it's not quite true that we +ACI-nowhere+ACI- give the exact range. Many of the examples give the actual Taylor model, and from a rough estimate of the range of the polynomial (for example by rastering), you can get a rather reasonable estimate of the overestimation you have.
+AD4- +AD4- Keep in mind too that you never have to range bound any
+AD4- +AD4- intermediate results, you leave them in the Taylor model form.
+AD4- +AD4- That's one of the tricks that helps so much in the verified integrators.
+AD4-
+AD4- This is what Hansen does in his recent Computing paper, but only with
+AD4- quadratic term.
I would be interested to see the final version of Hansen's paper. I had the pleasure to roughly discuss the matter with him about a year ago and much enjoyed it, but haven't seen the final product. From what I recall the method seemed a little similar to linear Taylor models. But in any case, if we have details we can also include it in the list of things to try.
+AD4- It is what I guess is the +ACo-only+ACo- trick that makes
+AD4- the Taylor model form in the form you propose useful,
+AD4- but I found this nowhere spelled out as such.
You don't find this spelled out because it is NOT the +ACo-only+ACo- trick that makes the Taylor model form useful. To begin with, the higher orders also matter+ACE- You can see this clearly with the Gritton problem and in many other cases+ADs- I hope in the course of this discussion, we will be able to get this point across fully clearly. And for all of the non-range bounding topics mentioned above, you really like the high orders because they give you more rapid convergence.
+AD4-
+AD4- +AD4- what's left to bound is some kind of higher order part+ADs-
+AD4- +AD4- and even if you use just plain intervals for that,
+AD4- +AD4- the overestimation of the true range is usually in the range of
+AD4- +AD4- a few percent only.
+AD4-
+AD4- I agree here+ADs- but this sounds quite different from your high order claims
+AD4- - it does not go down to a few millionth if you increase the order+ACE-
YES, IT DOES go down to a few millionths+ACE- The problem of the normal form problem is that of any typical dependency problem. By the time you have gotten the final Taylor model, all the bad cancellations HAVE ALREADY HAPPENED in the Taylor polynomials, WHERE THEY DIDN'T HURT in the process. And in the end, the Taylor polynomial has REASONABLY SMALL coefficients, reflecting the fact that in fact the function is reasonably small compared to its interval evaluatoin. But in the intermediate steps the coefficients were all very large, they just cancel each other in the end. This is precisely what happens in any of the blow-up based problems where Taylor models are useful. In fact, with the 6D normal form / invariant defect problem in particular, it REALLY doesn't matter how you bound your polynomial in the end, you will get the few millionths.
+AD4-
+AD4- +AD4- However, if you REALLY want to, and for the sake of the theoretical
+AD4- +AD4- argument, you CAN ALSO BOUND THE POLYNOMIAL of the Taylor model with
+AD4- +AD4- an overestimation that truly scales with order (n+-1) like the remainder.
+AD4-
+AD4- You say it now, but never in your publications, that this needs
+AD4- additional techniques (and you don't provide these techniques+ACE-).
+AD4- What you wrote in print always sounded like your method solved these
+AD4- problems already,
Well, what we were saying in the publications is something like +ACI-the remainder bound scales with order (n+-1)+ACI-, or +ACI-the approximation by the polynomial scales with order (n+-1)+ACI-, which is certainly true. For the sub-problem of range bounding, a little more thought (see above) is needed.
+AD4- and the interested reader (and more readers than you
+AD4- think are sophisticated enough that they don't need to get the same
+AD4- starter every time,
Again, sorry if anybody was reading the same thing repeatedly
+AD4- and don't notice that they are never served the real meat)
+AD4- is left to wonder what precisely is the degree of reliability of your
+AD4- statements. (It is better to claim less than to raise expectations
+AD4- that cannot be satisfied. In the past, the image of interval methods
+AD4- suffered severely from initial overenthusiasm that turned interested
+AD4- people away, or even hostile, when they noticed that the claims
+AD4- were not substantiated.)
+AD4-
Yes, I agree one has to be careful about not raising expectations+ADs- yet I also hope that the above paragraph didn't try to express a fundamental doubt about the reliability of my statements. Anyway, if at the end of this long and at times frustrating but hopefully ultimately useful discussion, it turns out that there was something we severely oversold, then I'll apologize and make my journey to Canossa ... ok? But what I claim, and many others agree now, and George said it from the beginning of this recent discussion: the polynomial bounding ISN't the real meat of the Taylor model approach+ACE- The ability to control the dependency problem is the key issue at hand here, and that happens via the use of floating point coefficients long before you get to the bounding of the final range. Furthermore, most of the time you can get order (n+-1) convergence not only in the enclosure of the function through its Taylor model, but also for predicted range bounds.
+AD4- +AD4- it ONLY works for Taylor polynomials where the contributions of the
+AD4- +AD4- higher orders fall off quickly, which however is what we have in
+AD4- +AD4- Taylor models.
+AD4-
+AD4- Only for high order terms+ACE- Nothing guarantees that for a general
+AD4- function, the quadratic contribution is already small. If I give you
+AD4- a homogeneous quadratic form in 6 variables to be enclosed in
+AD4- +AFs--0.05,0.05+AF0-,
+AD4- the Taylor form of order n+AD0-5 is the original function, and I want to see
+AD4- your method that provides an overestimation that truly scales with order
+AD4- n+-1.
+AD4-
Perhaps from the statements above it is clear what I mean now.
+AD4-
+AD4- +AD4- +ACI-The Taylor model method provides an asymptotic accuracy equal to
+AD4- +AD4- min(n+-1,p), where n is the order of the Taylor polynomial,
+AD4- +AD4- and p the order of the scheme used for bounding the Taylor polynomial.
+AD4- +AD4- If mere interval evaluation of the polynomial is used, then p+AD0-2,
+AD4- +AD4- as for all naive interval bounding. But various more efficient
+AD4- +AD4- polynomial bounding schemes exist with p higher than 2 exist. +ACI-
+AD4-
+AD4- In this form, your statement is correct. But my earlier statement,
+AD4-
+AD4- +AD4- the Taylor model only has the quadratic approximation property,
+AD4-
+AD4- was correct, too, for any of the versions of the Taylor model you
+AD4- presented (for dimension +AD4-1) in any of your publications,
+AD4- including Makino's thesis.
Again, perhaps the above statements clarify what is meant. If not, anybody please feel free to ask again and we'll take another round at it.
+AD4-
+AD4- Nataraj's achievement consists in making the Taylor model truly of
+AD4- higher order.
I have received pdf's of Prof. Nataraj's paper, but haven't had a chance to read it (as said above, even if it may sound hard to believe, there is life outside the interval world that also needs to be tended to +ADs--) ). However, if it's truly a general and efficient polynomial bounder, then it's definitely a useful asset to have.
Now, in order to focus this discussion back as much as possible to the science and away from the hot air, may I propose the following. Let us start with a simple example that has overestimation but that everybody who wants can handle easily+ADs- perhaps Gritton G(x). Next, we can proceed to a more complicated example, perhaps multidimensional Gritton G(ax+-by) etc., or if we want to, the normal form invariant defect problem - any other good suggestions? Everybody can use it to show their methods. Kyoko and I do it with Taylor models+ADs- if somebody (Arnold?) has code readily available, (s)he could run it with centered forms, affine arithmetic, Hansens's method, and whatever else can be done. If nobody has code for it, we here or Kyoko can probably try to put it together for the simpler schemes, but it may take a short time to do so. For the Taylor models, we can use different bounding schemes, beginning from trivial interval evaluation, then the default bounder, then the high-order linear dominated bounder, and perhaps also the bounders of Prof. Nataraj, with his help.
We will start with this as soon as I have contact with Makino again (I believe she is back from her trip now) and keep you posted.
Best wishes to all,
Martin
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 13 14:55:30 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2DKtTs11472
for reliable_computing-outgoing; Wed, 13 Mar 2002 14:55:29 -0600 (CST)
Received: from harpia.petrobras.com.br (harpia.petrobras.com.br [200.255.28.1])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2DKtM311468
for ; Wed, 13 Mar 2002 14:55:23 -0600 (CST)
Received: by harpia.petrobras.com.br; (8.8.8/1.3/10May95) id RAA16337; Wed, 13 Mar 2002 17:53:04 -0300 (GMT-0300)
From:
Subject: Interval Linear Systems of Equations - Overestimation - Help !!
To: "interval"
X-Mailer: Lotus Notes Release 5.0.2c (Intl)8 Fevereiro 2000
Message-ID:
Date: Wed, 13 Mar 2002 17:50:42 -0300
X-MIMETrack: Serialize by Router on CENPESLN01/CENPES/C/Petrobras(Release 5.07a |May 14, 2001) at
13/03/2002 17:50:42
MIME-Version: 1.0
Content-type: text/plain; charset=us-ascii
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear colleagues,
I am trying to solve a 1D heat conduction problem by FInite Elements
Method ( Ax=b). My stiffness matrix (A) is 51 x 51 ( row, column). This
example accessories my Phd thesis.
I am using the thermal conductivity (k) as interval number, with a little
variation in k I get a large overestimation in the results.
I have already tried the Preconditioning Gauss Elimination and Gauss-Seidel
Methods, the Combinatorial and the Powell Optimization Method.
Do anybody know how to treat and avoid this so large overestimation ?
Papers, routines, books an examples are welcome.
Best Regards,
Thank you very much.
Sebastiao Pereira
Petrobras - Brazilian Oil Company
http://www.petrobras.com.br
phone: 55 21 38656436
fax: 55 21 3865 6441
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 13 22:17:35 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2E4HYc12270
for reliable_computing-outgoing; Wed, 13 Mar 2002 22:17:34 -0600 (CST)
Received: from gcet_int.gcet.ac.in ([210.212.139.36])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2E4HN312266
for ; Wed, 13 Mar 2002 22:17:25 -0600 (CST)
Received: from KK ([10.10.10.12]) by gcet_int.gcet.ac.in with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2653.13)
id GY45N2K6; Wed, 13 Mar 2002 13:41:59 +0530
Message-ID: <003201c1ca68$66127620$0c0a0a0a@kk>
From: "Mr. Ketan Kotecha"
To:
References: +ADw-NEBBJIKHDMLBDKBEGMNEGEOLCCAA.nataraj+AEA-ee.iitb.ernet.in+AD4-
Subject: Fortran 90/95-timings
Date: Wed, 13 Mar 2002 13:53:41 +0530
MIME-Version: 1.0
Content-Type: text/plain;
charset="utf-7"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2919.6600
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear all:
Can any one tell me:, is that possible to get program execution timings in
milliseconds, or even in micro seconds, using microsoft fortran 90/Compaq
fortran/fortefortran 95?
I am getting it atmost accurately upto 1E-2 seconds.
Thanks in advance,
Ketan Kotecha
Research Scholar
IIT Bombay.
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 14 06:50:06 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2ECo5X13478
for reliable_computing-outgoing; Thu, 14 Mar 2002 06:50:05 -0600 (CST)
Received: from sunshine.math.utah.edu (IDENT:mk/dftbfX/M76F3t467afYOXViMYngxt [at] sunshine [dot] math.utah.edu [128.110.198.2])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2ECnw313474
for ; Thu, 14 Mar 2002 06:49:59 -0600 (CST)
Received: from suncore.math.utah.edu (IDENT:Zr1cJyJJN/d0V3B1G5m0ARxJkAuvR0KI [at] suncore0 [dot] math.utah.edu [128.110.198.5])
by sunshine.math.utah.edu (8.9.3/8.9.3) with ESMTP id FAA21272;
Thu, 14 Mar 2002 05:49:56 -0700 (MST)
Received: (from beebe@localhost)
by suncore.math.utah.edu (8.9.3/8.9.3) id FAA15054;
Thu, 14 Mar 2002 05:49:55 -0700 (MST)
Date: Thu, 14 Mar 2002 05:49:55 -0700 (MST)
From: "Nelson H. F. Beebe"
To: reliable_computing [at] interval [dot] louisiana.edu
Cc: beebe [at] math [dot] utah.edu, "Mr. Ketan Kotecha"
X-US-Mail: "Center for Scientific Computing, Department of Mathematics, 110
LCB, University of Utah, 155 S 1400 E RM 233, Salt Lake City, UT
84112-0090, USA"
X-Telephone: +1 801 581 5254
X-FAX: +1 801 585 1640, +1 801 581 4148
X-URL: http://www.math.utah.edu/~beebe
Subject: Re: Fortran 90/95-timings
In-Reply-To: Your message of Wed, 13 Mar 2002 13:53:41 +0530
Message-ID:
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
"Ketan Kotecha" asks on Wed, 13 Mar 2002 13:53:41
+0530 about getting program execution timings accurate to milliseconds
or better.
Sadly, on the vast majority of operating systems today, with clock
speeds sometimes exceeding 1GHz, process timers remain extremely
crude, with 60 to 100 ticks per second. This is true no matter what
programming language you use.
Some processors (DEC Alpha, IBM PowerPC, Intel Pentium, Sun
UltraSPARC) actually have timer instructions that can produce a
resolution of less than a microsec, but these tend to require kernel
privileges to execute, and remain unavailable to user processes, even
UNIX root (super-user) processes. Cray supercomputers have been about
the only ones I've encountered where accurate timing is available.
The workaround is to wrap benchmark codes with outer loops that repeat
the calculation long enough to get reliable timings, or use input data
that makes them run long enough. Of course, this doesn't work if you
are trying to accurately time various parts of real code.
If you delve into C header files, look for the symbols CLK_TCK,
CLOCKS_PER_SEC, HZ, and AHZ, and consult "man sysconf"; Sun Solaris
systems get CLK_TCK from the function call _sysconf(3).
On a GNU/Linux Red Hat 6.2 system on Intel x86, I find:
/* ISO/IEC 9899:1990 7.12.1:
The macro `CLOCKS_PER_SEC' is the number per second of the value
returned by the `clock' function.
CAE XSH, Issue 4, Version 2:
The value of CLOCKS_PER_SEC is required to be 1 million on all
XSI-conformant systems. */
# define CLOCKS_PER_SEC 1000000
/* Even though CLOCKS_PER_SEC has such a strange value CLK_TCK
presents the real value for clock ticks per second for the system. */
# define CLK_TCK 100
Thus, CLOCKS_PER_SEC may lie about the true timer resolution.
You also need to be aware of the effect of cache vs memory: the first
iteration your program runs, data may be in memory, but on subsequent
iterations, it may be in cache. The effect on timing can be dramatic.
Typically, register access takes 1 cycle, level-1 cache 2 to 5 cycles,
level-2 cache 8 to 15 cycles, and memory access 10 to 100 cycles. For
more details, see my February 2001 talk on microprocessors, starting
about slide 55, available at
http://www.chpc.utah.edu/cc/talks/beebe/index.htm
http://www.chpc.utah.edu/cc/talks/beebe/handout-color.pdf
Here is a copy of a file in which I recorded notes on 7-Oct-1996 about
timers on various systems when I implemented a profiling facility in
the awk programming language:
------------------------------------------------------------------------
These notes record my attempts to try to get access to a cheap
high-resolution clock for profiling on several systems.
------------------------------------------------------------------------
On Sun UltraSPARC, modified assembly code from timercheck.c
in function foo()
! 1 #include
! 2
! 3 typedef long long LONG;
! 4
! 5 LONG foo(void)
! 6 {
! 7 return (1000000L + sizeof(LONG));
sethi %hi(.L_cseg0),%l0
or %l0,%lo(.L_cseg0),%l0
ldd [%l0+0],%l0
std %l0,[%fp-8]
rd %tick,%l0 !<== inserted read of 63-bit cycle clock
ba .L76
nop
! block 2
.L76:
ldd [%fp-8],%l0
mov %l1,%i1
mov %l0,%i0
jmp %i7+8
restore
Compilation was
cc -c -xarch=v8plus timercheck.s
cc -o timercheck -xarch=v8plus timercheck.s
and running the job produces privilege failure, both as me, and as
root:
signal ILL (privileged opcode) in foo at 0x107e4
It is aggravating that such a useful instruction is locked out by the
operating system for `security reasons'.
Older SPARC architectures (pre-V9) lack any kind of a high-resolution
cycle timer.
------------------------------------------------------------------------
On the DEC Alpha, the rscc (read system cycle counter) is potentially
available in unprivileged VMS PALcode, but alas, not in OSF/1 PALcode.
------------------------------------------------------------------------
On the IBM RS/6000 PowerPC (see ``The PowerPC Architecture'', p. 354),
the 64-bit Time Base register can be read by a 5-instruction loop to
get a 64-bit value in two adjacent registers (r3 and r4 are needed for
a long long function return value). I modified the output assembly
code of timertest.c like this, to just read the lower 32 bits:
.foo: # 0x00000000 (H.10.NO_SYMBOL)
.file "timercheck.c"
cau r0,r0,0x0002
ai r3,r0,-31068
mftb r3 # <== inserted
bcr BO_ALWAYS,CR0_LT
This will not compile in the Power or Power2 architectures (-qarch=pwr
or -qarch=pwr2). It compiles in the PowerPC architecture
(-qarch=ppc), but on the Power and Power2 systems that I ran the test
on, it dies with
Illegal instruction (core dumped)
I don't have access to a PowerPC system running UNIX to make further
tests.
------------------------------------------------------------------------
The MIPS architecture does not appear to have any documented facility
for reading a high-precision clock, though on DEC ULTRIX, DEC OSF/1,
and SGI IRIX operating systems, the pixie/pixstats utilities appear to
be able to get exact cycle counts for instructions.
------------------------------------------------------------------------
I don't have online documentation of the HP-UX architecture to
investigate further on our HP workstations.
------------------------------------------------------------------------
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- Center for Scientific Computing FAX: +1 801 585 1640, +1 801 581 4148 -
- University of Utah Internet e-mail: beebe [at] math [dot] utah.edu -
- Department of Mathematics, 110 LCB beebe [at] acm [dot] org beebe [at] computer [dot] org -
- 155 S 1400 E RM 233 beebe [at] ieee [dot] org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe -
-------------------------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 14 17:47:09 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2ENl8S14666
for reliable_computing-outgoing; Thu, 14 Mar 2002 17:47:08 -0600 (CST)
Received: from patan.sun.com (patan.Sun.COM [192.18.98.43])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2ENkw314662
for ; Thu, 14 Mar 2002 17:46:59 -0600 (CST)
Received: from vic.Aus.Sun.COM ([129.158.87.25])
by patan.sun.com (8.9.3+Sun/8.9.3) with ESMTP id QAA17574
for ; Thu, 14 Mar 2002 16:46:55 -0700 (MST)
Received: from retreat (retreat [129.158.87.155])
by vic.Aus.Sun.COM (8.10.2+Sun/8.10.2/ENSMAIL,v2.2) with SMTP id g2ENkrh27825
for ; Fri, 15 Mar 2002 10:46:53 +1100 (EST)
Message-Id: <200203142346.g2ENkrh27825 [at] vic [dot] Aus.Sun.COM>
Date: Fri, 15 Mar 2002 10:47:44 +1100 (EST)
From: Richard Smith - Systems Engineer - Melbourne
Reply-To: Richard Smith - Systems Engineer - Melbourne
Subject: Re: Fortran 90/95-timings
To: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: jSDuc3Aonvn1JFX0DEK5MQ==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Following up on Nelson Beebe's comments, SPARC does indeed have a high
resolution clock that increments every cpu clock cycle. In the SPARC
architecture rdtick causes a privileged_action exception if PSTATE.PRIV = 0
and TICK.NPT = 1. From Solaris 7 onwards the default setting of the bits
permits rdtick in user code.
An alternative is to use the high resolution timer routine gethrtime(3C).
Admittedly it has higher overhead than rdtick but will work when threads get
migrated across multiple cpus. Depending on which method you use and the
specific cpu you're running on overhead is in the region of 10-100 cycles.
At a minimum rdtick stalls the cpu pipeline.
I tend to use inline(1) assembler code fragments to instrument code. Infact
it is possible to use a fragment to replace gethrtime with rdtick. Note the
different argument conventions required between v8 and v9:
gethrtimev8plus.il:
.inline gethrtime,0
rd %tick,%o0
sllx %o0,32,%o1
srlx %o0,32,%o0
srlx %o1,32,%o1
.end
gethrtimev9.il:
.inline gethrtime,0
rd %tick,%o0
.end
cc -fast gethrtimev8plus.il junk.c ...
Fortran code should use a pragma to specify that the "function" has a C
interface:
!$pragma C(gethrtime)
Related tricks can be used to exploit the hardware performance counters.
More information can be found in "Techniques For Optimizing Applications" by
Garg and Sharapov.
For Intel architecture I suggest consulting "Michael Abrash's Graphics
Programming Black Book" Ch 3 Zen Timer
http://www.ddj.com/documents/s=865/ddj0165f/
============================================================================
,-_|\ Richard Smith - SE Melbourne
/ \ Sun Microsystems Australia Phone : +61 3 9869 6200
richard.smith [at] Sun [dot] COM Direct : +61 3 9869 6224
\_,-._/ 476 St Kilda Road Fax : +61 3 9869 6290
v Melbourne Vic 3004 Australia
===========================================================================
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 15 18:33:50 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2G0Xnm17382
for reliable_computing-outgoing; Fri, 15 Mar 2002 18:33:49 -0600 (CST)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2G0Xi317378
for ; Fri, 15 Mar 2002 18:33:45 -0600 (CST)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.3/8.11.3) with SMTP id g2G0XdK24345;
Fri, 15 Mar 2002 17:33:39 -0700 (MST)
Message-Id: <200203160033.g2G0XdK24345 [at] cs [dot] utep.edu>
Date: Fri, 15 Mar 2002 17:33:37 -0700 (MST)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: conference in Bulgaria
To: reliable_computing [at] interval [dot] louisiana.edu
Cc: krat [at] bas [dot] bg
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: GYXAeYUX0hlhzmu5bbDsnA==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
FYI: Krassimir Atanassov is organizing a session on intuitionistic fuzzy sets
at the IEEE International Symposium 'Intelligent Systems'
Methodology, Models, Applications in Emerging Technologies
Hotel Palace, Sunny Day, Bulgaria, September 10-12, 2002
For this session, deadline was extended until the end of March. For details of
submission, check the conference's webpage http://www.iinf.bas.bg/is/
Right after the IEEE Conference, on September 12-13, there will be an annual
Conference on Intuitionistic Fuzzy Sets; the deadline for this conference is
May 31, 2002. Please contact Krassimir at krat [at] bas [dot] bg for details.
Vladik
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 20 10:19:20 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2KGJKQ00764
for reliable_computing-outgoing; Wed, 20 Mar 2002 10:19:20 -0600 (CST)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2KGJGr00760
for ; Wed, 20 Mar 2002 10:19:16 -0600 (CST)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.3/8.11.3) with SMTP id g2KGJBo18599;
Wed, 20 Mar 2002 09:19:11 -0700 (MST)
Message-Id: <200203201619.g2KGJBo18599 [at] cs [dot] utep.edu>
Date: Wed, 20 Mar 2002 09:19:10 -0700 (MST)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: Second call for participation
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: QPy0mxYcg20UJFBk8lO6Tg==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
deadline passed but they are still accepting abstracts
------------- Begin Forwarded Message -------------
To: jaf21 [at] pastor [dot] pdmi.ras.ru
From: "Alexei V. Pastor"
Date: Wed, 20 Mar 2002 14:38:55 +0300 (MSK)
Subject: Second call for participation
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Second call for participation
International meeting "21th DAYS OF WEAK ARITHMETICS"
June 7-9, 2002
St.Petersburg, Russia
MAIN TOPICS
For a detailed description of what are "Weak Arithmetics" visit
http://www.univ-paris12.fr/lacl/jaf/html/wa.html
The meeting will cover traditional topics of the "Days" such as:
Provability in weak arithmetics
Definability in weak arithmetics
Weak arithmetics and model theory
Decidability/undecidability of weak logical theories
Modelling computations in the frameworks of weak arithmetics
Weak arithmetics and computational comlexity
Computer science applications of weak arithmetics
Besides them a special session will be organized on:
Coding and processing information in biological systems
PERMANENT COMMITTEE of the DAYS:
Patrick CEGIELSKI Jean-Pierre RESSAYRE Denis RICHARD
University Paris-12 CNRS, Jussieu University of Auvergne
Fontainebleau IUT Clermont IUT, LLAIC1
PROGRAM COMMITTEE
Paola d'AQUINO (Italy)
Anatoly BELTIUKOV (Russia)
Patrick CEGIELSKI (France)
Gregory KUCHEROV (France)
Krzysztof LORYS (Poland)
Yuri MATIYASSEVICH (Russia), the chairman
Jean-Pierre RESSAYRE (France)
Denis RICHARD (France)
Maxim VSEMIRNOV (Russia)
Local ORGANIZING COMMITTEE :
Dmitri KARPOV Elena NOVIKOVA
Vladimir OREVKOV Alexei PASTOR
Yuri MATIYASEVICH (Head) Maxim VSEMIRNOV
Working LANGUAGE: English
SUBMISSION of papers
To this goal the facilities of Atlas Mathematical Conference Abstracts
will be used. If you wish to present a paper, please, submit an (extended)
abstract via
http://at.yorku.ca/cgi-bin/amca/submit/cail-01
following the instruction on this site. The deadline for
submission passed on March 15, 2002, if you want to
participate, submit your abstract as soon as possible.
REGISTRATION
Please, do it via http://logic.pdmi.ras.ru/jaf21/registration
Participation FEE:
The fee will cover common meals and coffee breaks (no return for possibly
non-taken meals). The fee equivalent to 120USD can be paid on arrival.
PLACE of the meeting:
The "21th DAYS" will be held at the Euler International Mathematical
Institute (which now is a part of St.Petersburg Department of Steklov
Institute of Mathematics of the Russian Academy of Sciences). The building
of the EIMI is situated at 10, Pesochnaya embankment.
ACCOMODATION
It is suggested that all participants stay at the nearby hotel of the
Palace of Youth (this is a standard place of living for visitors to the EIMI).
Current prices (slight increase is possible):
Single-room apartment for one persons: equivalent to 60 USD;
Single-room apartment for two persons: equivalent to 70 USD;
If you prefer to stay at another hotel (more or less expensive, or
closer to the center of the city), the Organizing Committee will help you
to find such accomodation.
Please, take into account that June is high tourist season in
St.Petersburg so rooms should be booked as soon as possible. You can do it
directly or we can do it for you (please, inform us if you are going to
share the room with particular person).
VISAS
Please, take into account that participants from the majority of
countries need visas to enrty Russia. After receiving your registration form,
the Organizing Committee will issue a proper invitation. Getting the visa
will take some time, so apply as soon as possible.
CONTACTS
Meeting's sites (mirrored):
http://logic.pdmi.ras.ru/jaf21
http://llaic3.u-clermont1.fr/~yumat/jaf21
E-mail: arithmet [at] logic [dot] pdmi.ras.ru
FAX: 7 (812) 310 53 77 (Program Committee)
7 (812) 234 58 19 (Organizing Committee)
Relevant LINKS :
All previous "Days":
http://www.univ-paris12.fr/lacl/jaf/html/issues.html
http://llaic3.u-clermont1.fr/E/jaf.htm
"14th Days" held also in St.Petersburg:
http://logic.pdmi.ras.ru/jaf14
Euler International Mathematical Institute:
http://www.pdmi.ras.ru/EIMI
Steklov Institute of Mathematics at St.Petersburg:
http://www.pdmi.ras.ru
Life in St.Petersburg:
http://www.spb.ru
--
Alexei Pastor
E-mail: pastor [at] pdmi [dot] ras.ru
------------- End Forwarded Message -------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 20 13:55:45 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2KJtiF01196
for reliable_computing-outgoing; Wed, 20 Mar 2002 13:55:44 -0600 (CST)
Received: from zeus.polsl.gliwice.pl (root [at] zeus [dot] polsl.gliwice.pl [157.158.1.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2KJtbr01192
for ; Wed, 20 Mar 2002 13:55:38 -0600 (CST)
Received: from andrzej1 (a18.asystent.polsl.gliwice.pl [157.158.187.18])
by zeus.polsl.gliwice.pl (8.9.3 (PHNE_25183)/8.9.3) with SMTP id UAA00859;
Wed, 20 Mar 2002 20:55:23 +0100 (MET)
Message-ID: <01d001c1d049$30752c60$0200a8c0@andrzej1>
From: "Andrzej Pownuk"
To: ,
Cc: "Andrzej Pownuk"
Subject: Re: Interval Linear Systems of Equations - Overestimation - Help !!
Date: Wed, 20 Mar 2002 20:55:24 +0100
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_01CD_01C1D051.8ECE07C0"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
This is a multi-part message in MIME format.
------=_NextPart_000_01CD_01C1D051.8ECE07C0
Content-Type: text/plain;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
I have worked on this problem since 1995.
Now I can solve system of 1000 equations with dependent interval =
parameters.
(I have solved system of 2300 equations=20
with two intervals Young's modulus.)
This algorithm can be downloaded directly from the internet.
http://157.158.187.18/papers/Interval_FEM.pdf
This algorithm was presented on the following conferences:
1) Pownuk A., Modelling of structures with uncertain parameters.
XLI Sympsion on Modeling in Mechanics,
18-22.02.2002, Wis=B3a, Poland
(Theoretical background)
2) Pownuk A., Numerical solutions of fuzzy partial differential equation =
and its application in computational mechanics.
Assessment and New Directions for Research.
FUZZY PARTIAL DIFFERENTIAL EQUATIONS,
FUZZY RELATIONAL EQUATIONS,
FUZZY DIFFERENCE EQUATIONS.
March 15-17, 2002
University of California-Berkeley ,
California 94720 - USA
(Applications)
Regards,
Andrzej Pownuk
...............................
Andrzej Pownuk
Chair of Theoretical Mechanics
Faculty of Civil Engineering
Silesian University of Technology
E-mail: pownuk [at] zeus [dot] polsl.gliwice.pl
URL: http://zeus.polsl.gliwice.pl/~pownuk/
...............................
>=20
> Dear colleagues,
>=20
> I am trying to solve a 1D heat conduction problem by FInite Elements
> Method ( Ax=3Db). My stiffness matrix (A) is 51 x 51 ( row, column). =
This
> example accessories my Phd thesis.
> I am using the thermal conductivity (k) as interval number, with a =
little
> variation in k I get a large overestimation in the results.
> I have already tried the Preconditioning Gauss Elimination and =
Gauss-Seidel
> Methods, the Combinatorial and the Powell Optimization Method.
> Do anybody know how to treat and avoid this so large overestimation ?
> Papers, routines, books an examples are welcome.
>=20
> Best Regards,
>=20
> Thank you very much.
>=20
> Sebastiao Pereira
> Petrobras - Brazilian Oil Company
> http://www.petrobras.com.br
> phone: 55 21 38656436
> fax: 55 21 3865 6441
>=20
>
------=_NextPart_000_01CD_01C1D051.8ECE07C0
Content-Type: text/html;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
I have worked on this problem since =
1995.
Now I=20
can solve system of 1000 equations with dependent interval =
parameters.
(I=20
have solved system of 2300 equations
with two intervals =
Young’s=20
modulus.)
This algorithm can be downloaded =
directly from the=20
internet.
This algorithm was presented on the following =
conferences:
1) Pownuk A., Modelling of structures with uncertain =
parameters.
XLI=20
Sympsion on Modeling in Mechanics,
18-22.02.2002, Wis=B3a,=20
Poland
(Theoretical background)
2) Pownuk A., Numerical solutions of fuzzy partial differential =
equation
and its application in computational =
mechanics.
Assessment and=20
New Directions for Research.
FUZZY PARTIAL DIFFERENTIAL =
EQUATIONS,
FUZZY=20
RELATIONAL EQUATIONS,
FUZZY DIFFERENCE EQUATIONS.
March 15-17,=20
2002
University of California-Berkeley ,
California 94720 -=20
USA
(Applications)
Regards,
&n=
bsp; =20
Andrzej Pownuk
>
> Dear colleagues,
>
> I am trying to =
solve a 1D=20
heat conduction problem by FInite Elements
> Method ( =
Ax=3Db). My=20
stiffness matrix (A) is 51 x 51 ( row, column). This
> example =
accessories=20
my Phd thesis.
> I am using the thermal conductivity (k) as =
interval=20
number, with a little
> variation in k I get a large =
overestimation in the=20
results.
> I have already tried the Preconditioning Gauss =
Elimination and=20
Gauss-Seidel
> Methods, the Combinatorial and the Powell=20
Optimization Method.
> Do anybody know how to treat and avoid this =
so=20
large overestimation ?
> Papers, routines, books an examples are=20
welcome.
>
> Best Regards,
>
> Thank you =
very=20
much.
>
> Sebastiao Pereira
> Petrobras - Brazilian =
Oil=20
Company
>
http://www.petrobras.com.br&=
gt;=20
phone: 55 21 38656436
> fax: 55 21 3865 6441
>=20
>
------=_NextPart_000_01CD_01C1D051.8ECE07C0--
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 20 14:53:38 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2KKrcf01351
for reliable_computing-outgoing; Wed, 20 Mar 2002 14:53:38 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2KKrWr01346
for ; Wed, 20 Mar 2002 14:53:33 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g2KKrJB07560;
Wed, 20 Mar 2002 15:53:19 -0500 (EST)
Message-ID: <003701c1d050$d30a1920$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore"
To: "Andrzej Pownuk"
Cc: "interval"
References: <01d001c1d049$30752c60$0200a8c0@andrzej1>
Subject: Re: Interval Linear Systems of Equations - Overestimation - Help !!
Date: Wed, 20 Mar 2002 15:50:09 -0500
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_0034_01C1D026.E9E024C0"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
This is a multi-part message in MIME format.
------=_NextPart_000_0034_01C1D026.E9E024C0
Content-Type: text/plain;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
Dear Andrzej,
I am very interested in your work and would very much like to read the =
publications you refer to below, however I am unable to open the =
download from the URL you give below.
Perhaps there is another version as a pdf file that I could open and =
read?
[Can anyone else in the reliable_computing group help with this?]
best wishes,
Ramon Moore
----- Original Message -----=20
From: Andrzej Pownuk=20
To: reliable_computing [at] interval [dot] louisiana.edu ; =
sebastiaoc [at] cenpes [dot] petrobras.com.br=20
Cc: Andrzej Pownuk=20
Sent: Wednesday, March 20, 2002 2:55 PM
Subject: Re: Interval Linear Systems of Equations - Overestimation - =
Help !!
I have worked on this problem since 1995.
Now I can solve system of 1000 equations with dependent interval =
parameters.
(I have solved system of 2300 equations=20
with two intervals Young's modulus.)
This algorithm can be downloaded directly from the internet.
http://157.158.187.18/papers/Interval_FEM.pdf
This algorithm was presented on the following conferences:
1) Pownuk A., Modelling of structures with uncertain parameters.
XLI Sympsion on Modeling in Mechanics,
18-22.02.2002, Wis=B3a, Poland
(Theoretical background)
2) Pownuk A., Numerical solutions of fuzzy partial differential =
equation=20
and its application in computational mechanics.
Assessment and New Directions for Research.
FUZZY PARTIAL DIFFERENTIAL EQUATIONS,
FUZZY RELATIONAL EQUATIONS,
FUZZY DIFFERENCE EQUATIONS.
March 15-17, 2002
University of California-Berkeley ,
California 94720 - USA
(Applications)
Regards,
Andrzej Pownuk
...............................
Andrzej Pownuk
Chair of Theoretical Mechanics
Faculty of Civil Engineering
Silesian University of Technology
E-mail: pownuk [at] zeus [dot] polsl.gliwice.pl
URL: http://zeus.polsl.gliwice.pl/~pownuk/
...............................
>=20
> Dear colleagues,
>=20
> I am trying to solve a 1D heat conduction problem by FInite =
Elements
> Method ( Ax=3Db). My stiffness matrix (A) is 51 x 51 ( row, column). =
This
> example accessories my Phd thesis.
> I am using the thermal conductivity (k) as interval number, with a =
little
> variation in k I get a large overestimation in the results.
> I have already tried the Preconditioning Gauss Elimination and =
Gauss-Seidel
> Methods, the Combinatorial and the Powell Optimization Method.
> Do anybody know how to treat and avoid this so large overestimation =
?
> Papers, routines, books an examples are welcome.
>=20
> Best Regards,
>=20
> Thank you very much.
>=20
> Sebastiao Pereira
> Petrobras - Brazilian Oil Company
> http://www.petrobras.com.br
> phone: 55 21 38656436
> fax: 55 21 3865 6441
>=20
>
------=_NextPart_000_0034_01C1D026.E9E024C0
Content-Type: text/html;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
Dear Andrzej,
I am very interested in your work and would very =
much like=20
to read the publications you refer to below, however I am unable to open =
the=20
download from the URL you give below.
Perhaps there is another version as a pdf file =
that I=20
could open and read?
[Can anyone else in the reliable_computing group =
help with=20
this?]
best wishes,
Ramon Moore
----- Original Message -----
Sent: Wednesday, March 20, 2002 =
2:55=20
PM
Subject: Re: Interval Linear =
Systems of=20
Equations - Overestimation - Help !!
I have worked on this problem since =
1995.
Now=20
I can solve system of 1000 equations with dependent interval =
parameters.
(I=20
have solved system of 2300 equations
with two intervals =
Young’s=20
modulus.)
This algorithm can be downloaded =
directly from=20
the internet.
This algorithm was presented on the following =
conferences:
1) Pownuk A., Modelling of structures with uncertain =
parameters.
XLI=20
Sympsion on Modeling in Mechanics,
18-22.02.2002, Wis=B3a,=20
Poland
(Theoretical background)
2) Pownuk A., Numerical solutions of fuzzy partial =
differential=20
equation
and its application in computational =
mechanics.
Assessment and=20
New Directions for Research.
FUZZY PARTIAL DIFFERENTIAL =
EQUATIONS,
FUZZY=20
RELATIONAL EQUATIONS,
FUZZY DIFFERENCE EQUATIONS.
March 15-17,=20
2002
University of California-Berkeley ,
California 94720 -=20
USA
(Applications)
Regards,
=
&n=
bsp; =20
Andrzej Pownuk
>
> Dear colleagues,
>
> I am trying to =
solve a 1D=20
heat conduction problem by FInite Elements
> Method ( =
Ax=3Db). My=20
stiffness matrix (A) is 51 x 51 ( row, column). This
> example=20
accessories my Phd thesis.
> I am using the thermal conductivity =
(k) as=20
interval number, with a little
> variation in k I get a large=20
overestimation in the results.
> I have already tried the=20
Preconditioning Gauss Elimination and Gauss-Seidel
> =
Methods, the=20
Combinatorial and the Powell Optimization Method.
> Do anybody =
know how=20
to treat and avoid this so large overestimation ?
> Papers, =
routines,=20
books an examples are welcome.
>
> Best Regards,
> =
>=20
Thank you very much.
>
> Sebastiao Pereira
>=20
Petrobras - Brazilian Oil Company
>
http://www.petrobras.com.br&=
gt;=20
phone: 55 21 38656436
> fax: 55 21 3865 6441
>=20
>
------=_NextPart_000_0034_01C1D026.E9E024C0--
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Mar 20 15:48:58 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2KLmv301504
for reliable_computing-outgoing; Wed, 20 Mar 2002 15:48:57 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2KLmqr01500
for ; Wed, 20 Mar 2002 15:48:52 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g2KLmpB14662
for ; Wed, 20 Mar 2002 16:48:51 -0500 (EST)
Message-ID: <009901c1d058$91a825a0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore"
To: "interval"
Subject: sorry, my problem
Date: Wed, 20 Mar 2002 16:45:35 -0500
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_0096_01C1D02E.A89FC300"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
This is a multi-part message in MIME format.
------=_NextPart_000_0096_01C1D02E.A89FC300
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Dear People,
Sorry for the trouble. The problem was at my end. I have the paper =
Interval_FEM.pdf
now.
Thanks for your help
Ramon Moore
------=_NextPart_000_0096_01C1D02E.A89FC300
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Dear People,
Sorry for the trouble. The problem was at my =
end. I have=20
the paper Interval_FEM.pdf
now.
Thanks for your help
Ramon Moore
------=_NextPart_000_0096_01C1D02E.A89FC300--
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 06:16:47 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LCGku05980
for reliable_computing-outgoing; Thu, 21 Mar 2002 06:16:46 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LCGer05976
for ; Thu, 21 Mar 2002 06:16:41 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g2LCDqZW152222;
Thu, 21 Mar 2002 13:13:53 +0100
Message-ID: <3C99CE80.8B9DA49B [at] univie [dot] ac.at>
Date: Thu, 21 Mar 2002 13:13:52 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] louisiana.edu
CC: sebastiaoc [at] cenpes [dot] petrobras.com.br
Subject: Re: Interval Linear Systems of Equations
References: <01d001c1d049$30752c60$0200a8c0@andrzej1>
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
> Andrzej Pownuk wrote:
>
> I have worked on this problem since 1995.
> Now I can solve system of 1000 equations with dependent interval
> parameters.
> (I have solved system of 2300 equations
> with two intervals Young?s modulus.)
>
> This algorithm can be downloaded directly from the internet.
>
> http://157.158.187.18/papers/Interval_FEM.pdf
However, your algorithm depends on unverified assumptions (after (3)),
that are unlikely to be satisfied if the intervals are wide.
To make this a valid algorithm you need to provide verifiable
sufficient conditions.
Moreover, the statement on p.3 is simply wrong.
You should have been suspicious about your method and proof,
since it would show polynomiality of a NP-hard problem - thus you
would have won one of the Millenium prizes (for P=NP) with such a
simple argument!
I think Jansson and Rohn wrote papers on linear interval systems with
linear dependence relations and narrow intervals, also based on
monotony arguments, that are on a sounder basis, and give *reliable*
results. Maybe someone can give precise references.
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 07:02:37 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LD2ag06191
for reliable_computing-outgoing; Thu, 21 Mar 2002 07:02:36 -0600 (CST)
Received: from rztsun.rz.tu-harburg.de (rztsun.rz.tu-harburg.de [134.28.200.14])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LD2Wr06187
for ; Thu, 21 Mar 2002 07:02:32 -0600 (CST)
Received: from hp0.mat.tu-harburg.de (hp0.mat.tu-harburg.de [134.28.61.10])
by rztsun.rz.tu-harburg.de (8.9.0/8.8.8) with ESMTP id NAA10919;
Thu, 21 Mar 2002 13:55:44 +0100 (MET)
Received: from zemke.mat.tu-harburg.de (zemke.mat.tu-harburg.de [134.28.61.33]) by hp0.mat.tu-harburg.de with ESMTP (8.9.3 (PHNE_24419)/8.7.1) id NAA25959; Thu, 21 Mar 2002 13:55:44 +0100 (MET)
Date: Thu, 21 Mar 2002 13:54:53 +0100 (MET)
From: Jens Zemke
X-X-Sender:
To: Arnold Neumaier
cc: ,
Subject: Re: Interval Linear Systems of Equations
In-Reply-To: <3C99CE80.8B9DA49B [at] univie [dot] ac.at>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
The precise reference to the Jansson/Rohn paper is
C. Jansson and J. Rohn. An Algorithm for
Checking Regularity of Interval Matrices.
SIAM J. Matrix Anal. Appl., 20(3):756-776, 1999.
It is a new version of
C. Jansson and J. Rohn. An Algorithm for
Checking Regularity of Interval Matrices.
Technical Report 96.4, Berichte des
Forschungsschwerpunktes Informations-
und Kommunikationstechnik, TUHH, 1996.
Also of interest might be
C. Jansson. Calculation of Exact Bounds
for the Solution Set of Linear Interval
Systems. Linear Algebra and its
Applications 251, 251:321-340, 1997.
Concerning dependent data the article
S.M. Rump. Verification Methods for
Dense and Sparse Systems of Equations.
In J. Herzberger, editor, Topics in
Validated Computations --- Studies in
Computational Mathematics, pages 63-136,
Elsevier, Amsterdam, 1994
might be of interest, especially p. 106 on
data dependencies in the input data.
Jens Zemke
- --
Jens-Peter M. Zemke -- zemke@tu-harburg.de
AB Mathematik / Mathematics Department
Technische Universitaet Hamburg -- Harburg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: Weitere Infos: siehe http://www.gnupg.org
iD8DBQE8mdgl04CU2LVV1ggRAtUTAJ9l3sZymUXuKPS2zS8ikSM/8XkbDgCfYqbE
gFrhMXC5zbzGOTbLWDof2bQ=
=8afB
-----END PGP SIGNATURE-----
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 09:00:27 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LF0Qc06474
for reliable_computing-outgoing; Thu, 21 Mar 2002 09:00:26 -0600 (CST)
Received: from zeus.polsl.gliwice.pl (root [at] zeus [dot] polsl.gliwice.pl [157.158.1.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LF0Kr06470
for ; Thu, 21 Mar 2002 09:00:21 -0600 (CST)
Received: from andrzej1 (a18.asystent.polsl.gliwice.pl [157.158.187.18])
by zeus.polsl.gliwice.pl (8.9.3 (PHNE_25183)/8.9.3) with SMTP id PAA22896;
Thu, 21 Mar 2002 15:59:05 +0100 (MET)
Message-ID: <003501c1d0e8$f17c4d90$0200a8c0@andrzej1>
From: "Andrzej Pownuk"
To: ,
Cc: "Andrzej Pownuk"
References: +ADw-01d001c1d049+ACQ-30752c60+ACQ-0200a8c0+AEA-andrzej1+AD4- +ADw-3C99CE80.8B9DA49B+AEA-univie.ac.at+AD4-
Subject: Re: Interval Linear Systems of Equations
Date: Thu, 21 Mar 2002 15:59:02 +0100
MIME-Version: 1.0
Content-Type: text/plain;
charset="UTF-7"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
+AD4- +AD4- Andrzej Pownuk wrote:
+AD4- +AD4-
+AD4- +AD4- I have worked on this problem since 1995.
+AD4- +AD4- Now I can solve system of 1000 equations with dependent interval
+AD4- +AD4- parameters.
+AD4- +AD4- (I have solved system of 2300 equations
+AD4- +AD4- with two intervals Young?s modulus.)
+AD4- +AD4-
+AD4- +AD4- This algorithm can be downloaded directly from the internet.
+AD4- +AD4-
+AD4- +AD4- http://157.158.187.18/papers/Interval+AF8-FEM.pdf
+AD4-
+AD4- However, your algorithm depends on unverified assumptions (after (3)),
+AD4- that are unlikely to be satisfied if the intervals are wide.
+AD4- To make this a valid algorithm you need to provide verifiable
+AD4- sufficient conditions.
After point (3) I assume that the intervals are narrow.
(+IBw-in technical applications the intervals are usually narrow+IB0-)
Additionally for small intervals we can assume
that the solution is monotone and depend only on
the endpoints of the intervals.
There are a lot of papers, which are based on these assumptions.
Akpan U.O., Koko T.S., Orisamolu I.R., Gallant B.K.,
Practical fuzzy finite element analysis of structures,
Finite Elements in Analysis and Design, 38 (2000) 93-111
McWilliam S., Anti-optimization of uncertain structures
using interval analysis,
Computers and Structures, 79 (2000) 421-430
Noor A.K., Starnes J.H., Peters J.M.,
Uncertainty analysis of composite structures,
Computer methods in applied mechanics and engineering,
79 (2000) 413-232
Valliappan S., Pham T.D., Elasto-Plastic Finite Element Analysis
with Fuzzy Parameters, International Journal
for Numerical Methods in Engineering, 38 (1995) 531-548
etc.
+AD4-
+AD4- Moreover, the statement on p.3 is simply wrong.
+AD4- You should have been suspicious about your method and proof,
+AD4- since it would show polynomiality of a NP-hard problem - thus you
+AD4- would have won one of the Millenium prizes (for P+AD0-NP) with such a
+AD4- simple argument+ACE-
Unfortunately, you are right.
I apologize for this error
but I still think that this algorithm can give
good solution in the case of narrow intervals.
Regards,
Andrzej Pownuk
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 09:43:55 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LFhta06636
for reliable_computing-outgoing; Thu, 21 Mar 2002 09:43:55 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LFhnr06632
for ; Thu, 21 Mar 2002 09:43:50 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g2LFf6JO032940;
Thu, 21 Mar 2002 16:41:07 +0100
Message-ID: <3C99FF12.5E6987EB [at] univie [dot] ac.at>
Date: Thu, 21 Mar 2002 16:41:06 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: Andrzej Pownuk
CC: sebastiaoc [at] cenpes [dot] petrobras.com.br,
reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Interval Linear Systems of Equations
References: +ADw-01d001c1d049+ACQ-30752c60+ACQ-0200a8c0+AEA-andrzej1+AD4- +ADw-3C99CE80.8B9DA49B+AEA-univie.ac.at+AD4- <003501c1d0e8$f17c4d90$0200a8c0@andrzej1>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Andrzej Pownuk wrote:
> After point (3) I assume that the intervals are narrow.
> (in technical applications the intervals are usually narrow)
> Additionally for small intervals we can assume
> that the solution is monotone and depend only on
> the endpoints of the intervals.
>
> There are a lot of papers, which are based on these assumptions.
People in applications may well be satisfied with results based
on uncertain assumptions.
But in *reliable computing*, on whose mailing list you are posting,
the common denominator is that *all* assumptions going into the
calculations are *verified* (including the effects of rounding errors,
which are usually deemed irrelevant in practical applications, too).
If one uses a method that works if the intervals are narrow enough
one still needs to check whether the *particular* intervals in the
application are *narrow enough* for the method to work; one might
be well within the valid domain, or just outside. The reliability
of the result depends on the ability to perform such a check.
You are well advised to study the work of Jansson and of Rohn to
learn about techniques how to do such checking.
If one cannot check the assumptions, there is no need to use
verified methods at all; using interval techniques to get
approximate answers is wasted effort.
My recommendation to those satsified with a reasonable approximation
of a range is to do traditional approximate sensitivity analysis,
which is cheap and gives adequate results for all kinds of problems
in most applications with narrow intervals.
> I still think that this algorithm can give
> good solution in the case of narrow intervals.
You should call it 'good approximation', not 'good solution'.
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 09:46:36 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LFka506717
for reliable_computing-outgoing; Thu, 21 Mar 2002 09:46:36 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LFkUr06713
for ; Thu, 21 Mar 2002 09:46:31 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g2LFkQn02109;
Thu, 21 Mar 2002 10:46:26 -0500 (EST)
Message-ID: <003801c1d0ef$1fea6260$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore"
To: "Andrzej Pownuk"
Cc: "interval"
References: +ADw-01d001c1d049+ACQ-30752c60+ACQ-0200a8c0+AEA-andrzej1+AD4- +ADw-3C99CE80.8B9DA49B+AEA-univie.ac.at+AD4- +ADw-003501c1d0e8+ACQ-f17c4d90+ACQ-0200a8c0+AEA-andrzej1+AD4-
Subject: Re: Interval Linear Systems of Equations
Date: Thu, 21 Mar 2002 10:43:18 -0500
MIME-Version: 1.0
Content-Type: text/plain;
charset="UTF-7"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear Colleagues,
Andrzej Pownuk makes an important point in reminding us that in many
practical applications
intervals are narrow.
Ramon Moore
----- Original Message -----
From: +ACI-Andrzej Pownuk+ACI- +ADw-pownuk+AEA-zeus.polsl.gliwice.pl+AD4-
To: +ADw-sebastiaoc+AEA-cenpes.petrobras.com.br+AD4AOw-
+ADw-reliable+AF8-computing+AEA-interval.louisiana.edu+AD4-
Cc: +ACI-Andrzej Pownuk+ACI- +ADw-pownuk+AEA-zeus.polsl.gliwice.pl+AD4-
Sent: Thursday, March 21, 2002 9:59 AM
Subject: Re: Interval Linear Systems of Equations
+AD4- +AD4- +AD4- Andrzej Pownuk wrote:
+AD4- +AD4- +AD4-
+AD4- +AD4- +AD4- I have worked on this problem since 1995.
+AD4- +AD4- +AD4- Now I can solve system of 1000 equations with dependent interval
+AD4- +AD4- +AD4- parameters.
+AD4- +AD4- +AD4- (I have solved system of 2300 equations
+AD4- +AD4- +AD4- with two intervals Young?s modulus.)
+AD4- +AD4- +AD4-
+AD4- +AD4- +AD4- This algorithm can be downloaded directly from the internet.
+AD4- +AD4- +AD4-
+AD4- +AD4- +AD4- http://157.158.187.18/papers/Interval+AF8-FEM.pdf
+AD4- +AD4-
+AD4- +AD4- However, your algorithm depends on unverified assumptions (after (3)),
+AD4- +AD4- that are unlikely to be satisfied if the intervals are wide.
+AD4- +AD4- To make this a valid algorithm you need to provide verifiable
+AD4- +AD4- sufficient conditions.
+AD4-
+AD4- After point (3) I assume that the intervals are narrow.
+AD4- (+IBw-in technical applications the intervals are usually narrow+IB0-)
+AD4- Additionally for small intervals we can assume
+AD4- that the solution is monotone and depend only on
+AD4- the endpoints of the intervals.
+AD4-
+AD4- There are a lot of papers, which are based on these assumptions.
+AD4-
+AD4- Akpan U.O., Koko T.S., Orisamolu I.R., Gallant B.K.,
+AD4- Practical fuzzy finite element analysis of structures,
+AD4- Finite Elements in Analysis and Design, 38 (2000) 93-111
+AD4-
+AD4- McWilliam S., Anti-optimization of uncertain structures
+AD4- using interval analysis,
+AD4- Computers and Structures, 79 (2000) 421-430
+AD4-
+AD4- Noor A.K., Starnes J.H., Peters J.M.,
+AD4- Uncertainty analysis of composite structures,
+AD4- Computer methods in applied mechanics and engineering,
+AD4- 79 (2000) 413-232
+AD4-
+AD4- Valliappan S., Pham T.D., Elasto-Plastic Finite Element Analysis
+AD4- with Fuzzy Parameters, International Journal
+AD4- for Numerical Methods in Engineering, 38 (1995) 531-548
+AD4-
+AD4- etc.
+AD4-
+AD4- +AD4-
+AD4- +AD4- Moreover, the statement on p.3 is simply wrong.
+AD4- +AD4- You should have been suspicious about your method and proof,
+AD4- +AD4- since it would show polynomiality of a NP-hard problem - thus you
+AD4- +AD4- would have won one of the Millenium prizes (for P+AD0-NP) with such a
+AD4- +AD4- simple argument+ACE-
+AD4-
+AD4- Unfortunately, you are right.
+AD4-
+AD4- I apologize for this error
+AD4- but I still think that this algorithm can give
+AD4- good solution in the case of narrow intervals.
+AD4-
+AD4- Regards,
+AD4-
+AD4- Andrzej Pownuk
+AD4-
+AD4-
+AD4-
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 10:29:47 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LGTk606888
for reliable_computing-outgoing; Thu, 21 Mar 2002 10:29:46 -0600 (CST)
Received: from imf09bis.bellsouth.net (mail309.mail.bellsouth.net [205.152.58.169])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LGTfr06884
for ; Thu, 21 Mar 2002 10:29:42 -0600 (CST)
Received: from u8174 ([66.20.82.156]) by imf09bis.bellsouth.net
(InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
id <20020321163055.SQXO26876.imf09bis.bellsouth.net@u8174>;
Thu, 21 Mar 2002 11:30:55 -0500
Message-Id: <2.2.32.20020321162923.00995c44 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 21 Mar 2002 10:29:23 -0600
To: "Ramon Moore" ,
"Andrzej Pownuk"
From: "R. Baker Kearfott"
Subject: Re: Interval Linear Systems of Equations
Cc: "interval"
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Colleagues,
Yes, indeed. And narrow intervals occur in diverse practical contexts,
when rigorous error bounds on a floating-point approximate solution
are desired. Depending on how the mathematics is done and how the
algorithms are arranged, working "in the small" can lead to much
nicer computational complexity.
Of course, it's easy for me to make such statements, but we need
to provide solid details :-)
Best regards,
Baker
At 10:43 AM 3/21/02 -0500, Ramon Moore wrote:
>Dear Colleagues,
>
>Andrzej Pownuk makes an important point in reminding us that in many
>practical applications
>intervals are narrow.
>
>Ramon Moore
>
---------------------------------------------------------------
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] louisiana.edu Thu Mar 21 10:58:03 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LGw3S07013
for reliable_computing-outgoing; Thu, 21 Mar 2002 10:58:03 -0600 (CST)
Received: from iph.bio.bas.bg (IDENT:0@bas-bio.lines.bas.bg [195.96.252.58])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LGvvr07009
for ; Thu, 21 Mar 2002 10:57:57 -0600 (CST)
Received: from biomath2 (biomath2.bio.bas.bg [195.96.247.143])
by iph.bio.bas.bg (8.11.6/8.9.3) with ESMTP id g2LGxBr19062
for ; Thu, 21 Mar 2002 18:59:11 +0200
From: "Evgenija D. Popova"
Organization: Institute of Mathematics & Informatics, BAS
To: reliable_computing [at] interval [dot] louisiana.edu
Date: Thu, 21 Mar 2002 19:02:49 +0100
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: Re: Interval Linear Systems of Equations
Reply-to: epopova [at] iph [dot] bio.bas.bg
Message-ID: <3C9A2E59.2127.1D30854@localhost>
In-reply-to: <3C99CE80.8B9DA49B [at] univie [dot] ac.at>
X-mailer: Pegasus Mail for Win32 (v3.12c)
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
The following paper:
E. Popova, Quality of the Solution Sets of Parameter-Dependent Interval
Linear Systems, to appear in ZAMM.
http://www.math.bas.bg/~epopova/papers/ZAMMPopova.pdf
contains some verifiable sufficient conditions for exact
finite characterisation of the bounds of the solution set
of a parametrised interval linear system.
In:
E.Popova, On the Solution of Parametrised Linear Systems.
W. Kraemer, J. Wolff von Gudenberg (Eds.): Scientific Computing,
Validated Numerics, Interval Methods. Kluwer Acad. Publishers, 2001,
pp. 127-138.
http://www.math.bas.bg/~epopova/papers/SCAN2000Popova.ps
on a practical example, we have presented our experience in
using Rump's algorithm and a way to sharpen the enclosing intervals
whenever it is necessary.
Evgenija D. Popova
---------------------------------------------------------
Institute of Mathematics & Informatics
Bulgarian Academy of Sciences
Acad. G. Bonchev str., block 8
BG-1113 Sofia, Bulgaria
Phone: (+359 2) 979-3704
Fax: (+359 2) 971-3649
http://www.math.bas.bg/~epopova
---------------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 11:13:47 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LHDlw07122
for reliable_computing-outgoing; Thu, 21 Mar 2002 11:13:47 -0600 (CST)
Received: from kathmandu.sun.com (kathmandu.sun.com [192.18.98.36])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LHDfr07118
for ; Thu, 21 Mar 2002 11:13:42 -0600 (CST)
Received: from engmail1.Eng.Sun.COM ([129.146.1.13])
by kathmandu.sun.com (8.9.3+Sun/8.9.3) with ESMTP id KAA11002;
Thu, 21 Mar 2002 10:13:36 -0700 (MST)
Received: from phys-mpkmaila (phys-mpkmaila.Eng.Sun.COM [129.146.18.131])
by engmail1.Eng.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v2.1p1) with ESMTP id JAA00770;
Thu, 21 Mar 2002 09:13:35 -0800 (PST)
Received: from nubbins (nubbins.Eng.Sun.COM [129.146.79.58])
by mpkmail.eng.sun.com (iPlanet Messaging Server 5.2 (built Jan 13 2002))
with SMTP id <0GTC00HN32JQOQ [at] mpkmail [dot] eng.sun.com>; Thu,
21 Mar 2002 09:14:15 -0800 (PST)
Date: Thu, 21 Mar 2002 09:13:35 -0800 (PST)
From: Marty Itzkowitz
Subject: Re: Fortran 90/95-timings
To: beebe [at] math [dot] utah.edu, reliable_computing [at] interval [dot] louisiana.edu,
kk [at] gcet [dot] ac.in
Cc: Martin.Itzkowitz [at] Eng [dot] Sun.COM, gvt [at] mpkmail [dot] eng.sun.com
Reply-to: Marty Itzkowitz
Message-id: <0GTC00HN42JROQ [at] mpkmail [dot] eng.sun.com>
MIME-version: 1.0
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc
Content-type: TEXT/plain; charset=us-ascii
Content-transfer-encoding: 7BIT
Content-MD5: ktf/lMCIpdpLCvqmHYePsg==
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
This email was forwarded to me by Gregory Tarsy.
There is a gethrtime(3C) routine available on Solaris that
will give very fast high-resolution timing. On my Ultra-60, the
gethrtime call takes approximately 300 nanoseconds.
Its man page reads as follows:
Standard C Library Functions gethrtime(3C)
NAME
gethrtime, gethrvtime - get high resolution time
SYNOPSIS
#include
hrtime_t gethrtime(void);
hrtime_t gethrvtime(void);
DESCRIPTION
The gethrtime() function returns the current high-resolution
real time. Time is expressed as nanoseconds since some arbi-
trary time in the past; it is not correlated in any way to
the time of day, and thus is not subject to resetting or
drifting by way of adjtime(2) or settimeofday(3C). The hi-
res timer is ideally suited to performance measurement
tasks, where cheap, accurate interval timing is required.
The gethrvtime() function returns the current high-
resolution LWP virtual time, expressed as total nanoseconds
of execution time. This function requires that micro state
accounting be enabled with the ptime utility (see proc(1)).
The gethrtime() and gethrvtime() functions both return an
hrtime_t, which is a 64-bit (long long) signed integer.
EXAMPLES
The following code fragment measures the average cost of
getpid(2):
hrtime_t start, end;
int i, iters = 100;
start = gethrtime();
for (i = 0; i < iters; i++)
getpid();
end = gethrtime();
printf("Avg getpid() time = %lld nsec\n", (end - start) / iters);
ATTRIBUTES
See attributes(5) for descriptions of the following attri-
butes:
____________________________________________________________
| ATTRIBUTE TYPE | ATTRIBUTE VALUE |
|_____________________________|_____________________________|
| MT-Level | MT-Safe |
|_____________________________|_____________________________|
SunOS 5.8 Last change: 10 Apr 1997 1
Standard C Library Functions gethrtime(3C)
SEE ALSO
proc(1), adjtime(2), gettimeofday(3C), settimeofday(3C),
attributes(5)
NOTES
Although the units of hi-res time are always the same
(nanoseconds), the actual resolution is hardware dependent.
Hi-res time is guaranteed to be monotonic (it won't go back-
ward, it won't periodically wrap) and linear (it won't occa-
sionally speed up or slow down for adjustment, like the time
of day can), but not necessarily unique: two sufficiently
proximate calls may return the same value.
SunOS 5.8 Last change: 10 Apr 1997 2
Marty Itzkowitz
Project Lead, Forte Developer Performance Tools
------------- Begin Forwarded Message -------------
Date: Thu, 14 Mar 2002 12:25:38 -0800 (PST)
From: "Gregory V. Tarsy"
Subject: Re: Fortran 90/95-timings
To: martyi [at] susila [dot] eng.sun.com
A query that you could answer ...
------------- Begin Forwarded Message -------------
Date: Thu, 14 Mar 2002 05:49:55 -0700 (MST)
From: "Nelson H. F. Beebe"
To: reliable_computing [at] interval [dot] louisiana.edu
Cc: beebe [at] math [dot] utah.edu, "Mr. Ketan Kotecha"
X-US-Mail: "Center for Scientific Computing, Department of Mathematics, 110 LCB,
University of Utah, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA"
X-Telephone: +1 801 581 5254
X-FAX: +1 801 585 1640, +1 801 581 4148
X-URL: http://www.math.utah.edu/~beebe
Subject: Re: Fortran 90/95-timings
"Ketan Kotecha" asks on Wed, 13 Mar 2002 13:53:41
+0530 about getting program execution timings accurate to milliseconds
or better.
Sadly, on the vast majority of operating systems today, with clock
speeds sometimes exceeding 1GHz, process timers remain extremely
crude, with 60 to 100 ticks per second. This is true no matter what
programming language you use.
Some processors (DEC Alpha, IBM PowerPC, Intel Pentium, Sun
UltraSPARC) actually have timer instructions that can produce a
resolution of less than a microsec, but these tend to require kernel
privileges to execute, and remain unavailable to user processes, even
UNIX root (super-user) processes. Cray supercomputers have been about
the only ones I've encountered where accurate timing is available.
The workaround is to wrap benchmark codes with outer loops that repeat
the calculation long enough to get reliable timings, or use input data
that makes them run long enough. Of course, this doesn't work if you
are trying to accurately time various parts of real code.
If you delve into C header files, look for the symbols CLK_TCK,
CLOCKS_PER_SEC, HZ, and AHZ, and consult "man sysconf"; Sun Solaris
systems get CLK_TCK from the function call _sysconf(3).
On a GNU/Linux Red Hat 6.2 system on Intel x86, I find:
/* ISO/IEC 9899:1990 7.12.1:
The macro `CLOCKS_PER_SEC' is the number per second of the value
returned by the `clock' function.
CAE XSH, Issue 4, Version 2:
The value of CLOCKS_PER_SEC is required to be 1 million on all
XSI-conformant systems. */
# define CLOCKS_PER_SEC 1000000
/* Even though CLOCKS_PER_SEC has such a strange value CLK_TCK
presents the real value for clock ticks per second for the system. */
# define CLK_TCK 100
Thus, CLOCKS_PER_SEC may lie about the true timer resolution.
You also need to be aware of the effect of cache vs memory: the first
iteration your program runs, data may be in memory, but on subsequent
iterations, it may be in cache. The effect on timing can be dramatic.
Typically, register access takes 1 cycle, level-1 cache 2 to 5 cycles,
level-2 cache 8 to 15 cycles, and memory access 10 to 100 cycles. For
more details, see my February 2001 talk on microprocessors, starting
about slide 55, available at
http://www.chpc.utah.edu/cc/talks/beebe/index.htm
http://www.chpc.utah.edu/cc/talks/beebe/handout-color.pdf
Here is a copy of a file in which I recorded notes on 7-Oct-1996 about
timers on various systems when I implemented a profiling facility in
the awk programming language:
------------------------------------------------------------------------
These notes record my attempts to try to get access to a cheap
high-resolution clock for profiling on several systems.
------------------------------------------------------------------------
On Sun UltraSPARC, modified assembly code from timercheck.c
in function foo()
! 1 #include
! 2
! 3 typedef long long LONG;
! 4
! 5 LONG foo(void)
! 6 {
! 7 return (1000000L + sizeof(LONG));
sethi %hi(.L_cseg0),%l0
or %l0,%lo(.L_cseg0),%l0
ldd [%l0+0],%l0
std %l0,[%fp-8]
rd %tick,%l0 !<== inserted read of 63-bit cycle clock
ba .L76
nop
! block 2
.L76:
ldd [%fp-8],%l0
mov %l1,%i1
mov %l0,%i0
jmp %i7+8
restore
Compilation was
cc -c -xarch=v8plus timercheck.s
cc -o timercheck -xarch=v8plus timercheck.s
and running the job produces privilege failure, both as me, and as
root:
signal ILL (privileged opcode) in foo at 0x107e4
It is aggravating that such a useful instruction is locked out by the
operating system for `security reasons'.
Older SPARC architectures (pre-V9) lack any kind of a high-resolution
cycle timer.
------------------------------------------------------------------------
On the DEC Alpha, the rscc (read system cycle counter) is potentially
available in unprivileged VMS PALcode, but alas, not in OSF/1 PALcode.
------------------------------------------------------------------------
On the IBM RS/6000 PowerPC (see ``The PowerPC Architecture'', p. 354),
the 64-bit Time Base register can be read by a 5-instruction loop to
get a 64-bit value in two adjacent registers (r3 and r4 are needed for
a long long function return value). I modified the output assembly
code of timertest.c like this, to just read the lower 32 bits:
.foo: # 0x00000000 (H.10.NO_SYMBOL)
.file "timercheck.c"
cau r0,r0,0x0002
ai r3,r0,-31068
mftb r3 # <== inserted
bcr BO_ALWAYS,CR0_LT
This will not compile in the Power or Power2 architectures (-qarch=pwr
or -qarch=pwr2). It compiles in the PowerPC architecture
(-qarch=ppc), but on the Power and Power2 systems that I ran the test
on, it dies with
Illegal instruction (core dumped)
I don't have access to a PowerPC system running UNIX to make further
tests.
------------------------------------------------------------------------
The MIPS architecture does not appear to have any documented facility
for reading a high-precision clock, though on DEC ULTRIX, DEC OSF/1,
and SGI IRIX operating systems, the pixie/pixstats utilities appear to
be able to get exact cycle counts for instructions.
------------------------------------------------------------------------
I don't have online documentation of the HP-UX architecture to
investigate further on our HP workstations.
------------------------------------------------------------------------
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- Center for Scientific Computing FAX: +1 801 585 1640, +1 801 581 4148 -
- University of Utah Internet e-mail: beebe [at] math [dot] utah.edu -
- Department of Mathematics, 110 LCB beebe [at] acm [dot] org beebe [at] computer [dot] org -
- 155 S 1400 E RM 233 beebe [at] ieee [dot] org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe -
-------------------------------------------------------------------------------
------------- End Forwarded Message -------------
------------- End Forwarded Message -------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 14:17:43 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LKHhm07495
for reliable_computing-outgoing; Thu, 21 Mar 2002 14:17:43 -0600 (CST)
Received: from smtp.sunflower.com (smtp.sunflower.com [24.124.0.128])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LKHcr07491
for ; Thu, 21 Mar 2002 14:17:39 -0600 (CST)
Received: from tirazezhk1exbw (dv137s77.lawrence.ks.us [24.124.77.137])
by smtp.sunflower.com (8.11.6/8.11.6) with SMTP id g2LKHbv26353
for ; Thu, 21 Mar 2002 14:17:37 -0600
Message-ID: <001b01c1d114$81125d20$6401a8c0@tirazezhk1exbw>
From: "tiraz birdie"
To:
References: <3C9A2E59.2127.1D30854@localhost>
Subject: Re: Interval Linear Systems of Equations
Date: Thu, 21 Mar 2002 14:10:48 -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 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
If my memory serves me right, then the heat conduction equation represents a
convex problem in the (conductivity) parameter space. Therefore, you can
obtain the bounds by simply using the upper and lower limits of the
parameter.
Tiraz Birdie
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 14:53:51 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LKrod07621
for reliable_computing-outgoing; Thu, 21 Mar 2002 14:53:50 -0600 (CST)
Received: from kathmandu.sun.com (kathmandu.sun.com [192.18.98.36])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LKrjr07617
for ; Thu, 21 Mar 2002 14:53:46 -0600 (CST)
Received: from engmail3.Eng.Sun.COM ([129.144.170.5])
by kathmandu.sun.com (8.9.3+Sun/8.9.3) with ESMTP id NAA12081;
Thu, 21 Mar 2002 13:53:39 -0700 (MST)
Received: from phys-mpkmaila (phys-mpkmaila.Eng.Sun.COM [129.146.18.131])
by engmail3.Eng.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v2.1p1) with ESMTP id MAA28694;
Thu, 21 Mar 2002 12:53:39 -0800 (PST)
Received: from gww (gww.Eng.Sun.COM [129.146.78.116])
by mpkmail.eng.sun.com (iPlanet Messaging Server 5.2 (built Jan 13 2002))
with SMTP id <0GTC00HZ1CQIOQ [at] mpkmail [dot] eng.sun.com>; Thu,
21 Mar 2002 12:54:18 -0800 (PST)
Date: Thu, 21 Mar 2002 12:53:38 -0800 (PST)
From: William Walster
Subject: Re: Interval Linear Systems of Equations
To: rmoore17 [at] columbus [dot] rr.com, pownuk [at] zeus [dot] polsl.gliwice.pl, rbk [at] louisiana [dot] edu
Cc: reliable_computing [at] interval [dot] louisiana.edu
Reply-to: William Walster
Message-id: <0GTC00HZ2CQIOQ [at] mpkmail [dot] eng.sun.com>
MIME-version: 1.0
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
Content-type: TEXT/plain; charset=us-ascii
Content-transfer-encoding: 7BIT
Content-MD5: Xy/rWcBDhiCc10Bs7i2fNw==
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Would it be possible to "cheaply" but rigorously verify if the
necessary assumptions have been met? This might be less work than
our normal procedures. With a contracting map, once the necessary
conditions have been satisfied, the tests should not be necessary.
Bill
>Date: Thu, 21 Mar 2002 10:29:23 -0600
>From: "R. Baker Kearfott"
>Subject: Re: Interval Linear Systems of Equations
>X-Sender: rbk5287 [at] pop [dot] louisiana.edu
>To: Ramon Moore , Andrzej Pownuk
>Cc: interval
>MIME-version: 1.0
>
>Colleagues,
>
>Yes, indeed. And narrow intervals occur in diverse practical contexts,
>when rigorous error bounds on a floating-point approximate solution
>are desired. Depending on how the mathematics is done and how the
>algorithms are arranged, working "in the small" can lead to much
>nicer computational complexity.
>
>Of course, it's easy for me to make such statements, but we need
>to provide solid details :-)
>
>Best regards,
>
>Baker
>
>At 10:43 AM 3/21/02 -0500, Ramon Moore wrote:
>>Dear Colleagues,
>>
>>Andrzej Pownuk makes an important point in reminding us that in many
>>practical applications
>>intervals are narrow.
>>
>>Ramon Moore
>>
>
>---------------------------------------------------------------
>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] louisiana.edu Thu Mar 21 15:55:15 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LLtFV07816
for reliable_computing-outgoing; Thu, 21 Mar 2002 15:55:15 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LLt9r07812
for ; Thu, 21 Mar 2002 15:55:10 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g2LLsuSi065322;
Thu, 21 Mar 2002 22:54:57 +0100
Message-ID: <3C9A56B0.C7CA176A [at] univie [dot] ac.at>
Date: Thu, 21 Mar 2002 22:54:56 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: William Walster
CC: rmoore17 [at] columbus [dot] rr.com, pownuk [at] zeus [dot] polsl.gliwice.pl, rbk [at] louisiana [dot] edu,
reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Interval Linear Systems of Equations
References: <0GTC00HZ2CQIOQ [at] mpkmail [dot] eng.sun.com>
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
William Walster wrote:
>
> Would it be possible to "cheaply" but rigorously verify if the
> necessary assumptions have been met? This might be less work than
> our normal procedures. With a contracting map, once the necessary
> conditions have been satisfied, the tests should not be necessary.
Hansen has an *old* paper in which he used *verified* monotony of some
components of an interval linear system to fix these components at a
bound
and showed that in the 'inverse stable' case, where all signs are fixed
(which holds with high probability if all intervals are narrow),
the total work is reduced to O(n^4); when the signs have special
patterns (which is the case only in special situations, even for thin
interval matrices) the work is even O(n^3) only. These cases correspond
precisely to the situation discussed by Pownuk on his faulty p.3.
Which sign patterns must be checked in the general case is stated
precisely in Corollary 6.2.4 of my book, following work of Rohn.
The *verification* of signs is based in both cases on the ability to
first compute an enclosure of the inverse of the interval coefficient
matrix, which is cheap, O(n^3), but limited to strongly regular
matrices.
This limitation is removed to some extent by Jansson and Rohn, I
believe.
Pownuk discusses (in the correct pages 1 and 2) also the case of
dependent interval coefficients (which was not considered by Hansen).
Probably his results are covered for linear dependences
by Jansson and Rohn, who give (for whatever results they actually have)
*verifiable* conditions. Since I have the papers not readily available,
I can't check at the moment what they actually did; maybe the authors
should summarize their main results here to make them more generally
known.
What is probably new about Pownuk's results is the generalization to
nonlinear parameter dependence, and the sign verification in this case
can
probably be done in analogy to what has been done in the linear case.
If done properly and written up with the same care as done by
Hansen, Rohn and Jansson, this will be a useful addition to the tool
set for linear interval equations. However, we should not fall below
already established standards of quality.
Best wishes,
Arnold
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu Mar 21 16:18:06 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LMI5p07934
for reliable_computing-outgoing; Thu, 21 Mar 2002 16:18:05 -0600 (CST)
Received: from kathmandu.sun.com (kathmandu.sun.com [192.18.98.36])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LMI0r07930
for ; Thu, 21 Mar 2002 16:18:01 -0600 (CST)
Received: from engmail1.Eng.Sun.COM ([129.146.1.13])
by kathmandu.sun.com (8.9.3+Sun/8.9.3) with ESMTP id PAA25666;
Thu, 21 Mar 2002 15:17:40 -0700 (MST)
Received: from phys-mpkmaila (phys-mpkmaila.Eng.Sun.COM [129.146.18.131])
by engmail1.Eng.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v2.1p1) with ESMTP id OAA27460;
Thu, 21 Mar 2002 14:17:39 -0800 (PST)
Received: from gww (gww.Eng.Sun.COM [129.146.78.116])
by mpkmail.eng.sun.com (iPlanet Messaging Server 5.2 (built Jan 13 2002))
with SMTP id <0GTC00EQXGMIMP [at] mpkmail [dot] eng.sun.com>; Thu,
21 Mar 2002 14:18:18 -0800 (PST)
Date: Thu, 21 Mar 2002 14:17:38 -0800 (PST)
From: William Walster
Subject: Re: Interval Linear Systems of Equations
To: Bill.Walster [at] Eng [dot] Sun.COM, Arnold.Neumaier [at] univie [dot] ac.at
Cc: rmoore17 [at] columbus [dot] rr.com, pownuk [at] zeus [dot] polsl.gliwice.pl, rbk [at] louisiana [dot] edu,
reliable_computing [at] interval [dot] louisiana.edu
Reply-to: William Walster
Message-id: <0GTC00EQYGMIMP [at] mpkmail [dot] eng.sun.com>
MIME-version: 1.0
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
Content-type: TEXT/plain; charset=us-ascii
Content-transfer-encoding: 7BIT
Content-MD5: i1c9i2NM4G8ZseM6Hm02OA==
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Great. Thanks, Arnold.
Of course, I *absolutely* agree with your last sentence :)
Cheers,
Bill
>Date: Thu, 21 Mar 2002 22:54:56 +0100
>From: Arnold Neumaier
>Subject: Re: Interval Linear Systems of Equations
>To: William Walster
>Cc: rmoore17 [at] columbus [dot] rr.com, pownuk [at] zeus [dot] polsl.gliwice.pl,
rbk [at] louisiana [dot] edu, reliable_computing [at] interval [dot] louisiana.edu
>MIME-version: 1.0
>Content-transfer-encoding: 7bit
>X-Accept-Language: en, de
>
>William Walster wrote:
>>
>> Would it be possible to "cheaply" but rigorously verify if the
>> necessary assumptions have been met? This might be less work than
>> our normal procedures. With a contracting map, once the necessary
>> conditions have been satisfied, the tests should not be necessary.
>
>Hansen has an *old* paper in which he used *verified* monotony of some
>components of an interval linear system to fix these components at a
>bound
>and showed that in the 'inverse stable' case, where all signs are fixed
>(which holds with high probability if all intervals are narrow),
>the total work is reduced to O(n^4); when the signs have special
>patterns (which is the case only in special situations, even for thin
>interval matrices) the work is even O(n^3) only. These cases correspond
>precisely to the situation discussed by Pownuk on his faulty p.3.
>
>Which sign patterns must be checked in the general case is stated
>precisely in Corollary 6.2.4 of my book, following work of Rohn.
>The *verification* of signs is based in both cases on the ability to
>first compute an enclosure of the inverse of the interval coefficient
>matrix, which is cheap, O(n^3), but limited to strongly regular
>matrices.
>This limitation is removed to some extent by Jansson and Rohn, I
>believe.
>
>Pownuk discusses (in the correct pages 1 and 2) also the case of
>dependent interval coefficients (which was not considered by Hansen).
>Probably his results are covered for linear dependences
>by Jansson and Rohn, who give (for whatever results they actually have)
>*verifiable* conditions. Since I have the papers not readily available,
>I can't check at the moment what they actually did; maybe the authors
>should summarize their main results here to make them more generally
>known.
>
>What is probably new about Pownuk's results is the generalization to
>nonlinear parameter dependence, and the sign verification in this case
>can
>probably be done in analogy to what has been done in the linear case.
>If done properly and written up with the same care as done by
>Hansen, Rohn and Jansson, this will be a useful addition to the tool
>set for linear interval equations. However, we should not fall below
>already established standards of quality.
>
>
>Best wishes,
>
>Arnold
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 22 05:56:29 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2MBuSi09594
for reliable_computing-outgoing; Fri, 22 Mar 2002 05:56:28 -0600 (CST)
Received: from sgu.ssu.runnet.ru (sgu.ssu.runnet.ru [212.193.32.14])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2MBoTr09581
for ; Fri, 22 Mar 2002 05:50:47 -0600 (CST)
Received: from info.sgu.ru (info.sgu.ru [212.193.32.6])
by sgu.ssu.runnet.ru (8.12.2/8.12.2) with ESMTP id g2MBlvrl065545
for ; Fri, 22 Mar 2002 14:47:57 +0300 (MSK)
Received: from info.sgu.ru ([212.193.39.42]) by info.sgu.ru
(Netscape Messaging Server 3.6) with SMTP id AAA2880
for ;
Fri, 22 Mar 2002 14:35:40 +0300
Status: U
Received: from sgu.ssu.runnet.ru ([212.193.32.14]) by info.sgu.ru (Netscape Messaging Server 3.6) with ESMTP id AAA53C3; Thu, 21 Mar 2002 19:52:46 +0300
Received: from interval.louisiana.edu (interval.louisiana.edu [130.70.132.145]) by sgu.ssu.runnet.ru (8.12.2/8.12.2) with ESMTP id g2LH3Irl034950; Thu, 21 Mar 2002 20:03:47 +0300 (MSK)
Received: from localhost (daemon@localhost) by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with SMTP id g2LH1Ga07092; Thu, 21 Mar 2002 11:01:17 -0600 (CST)
Received: (from daemon@localhost) by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2LGw3S07013 for reliable_computing-outgoing; Thu, 21 Mar 2002 10:58:03 -0600 (CST)
Received: from iph.bio.bas.bg (IDENT:0@bas-bio.lines.bas.bg [195.96.252.58]) by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2LGvvr07009 for ; Thu, 21 Mar 2002 10:57:57 -0600 (CST)
Received: from biomath2 (biomath2.bio.bas.bg [195.96.247.143]) by iph.bio.bas.bg (8.11.6/8.9.3) with ESMTP id g2LGxBr19062 for ; Thu, 21 Mar 2002 18:59:11 +0200
From: "Evgenija D. Popova"
Organization: Institute of Mathematics & Informatics, BAS
To: reliable_computing [at] interval [dot] louisiana.edu
Date: Thu, 21 Mar 2002 19:02:49 +0100
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: Re: Interval Linear Systems of Equations
Reply-to: epopova [at] iph [dot] bio.bas.bg
Message-ID: <3C9A2E59.2127.1D30854@localhost>
In-reply-to: <3C99CE80.8B9DA49B [at] univie [dot] ac.at>
X-mailer: Pegasus Mail for Win32 (v3.12c)
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
The following paper:
E. Popova, Quality of the Solution Sets of Parameter-Dependent Interval
Linear Systems, to appear in ZAMM.
http://www.math.bas.bg/~epopova/papers/ZAMMPopova.pdf
contains some verifiable sufficient conditions for exact
finite characterisation of the bounds of the solution set
of a parametrised interval linear system.
In:
E.Popova, On the Solution of Parametrised Linear Systems.
W. Kraemer, J. Wolff von Gudenberg (Eds.): Scientific Computing,
Validated Numerics, Interval Methods. Kluwer Acad. Publishers, 2001,
pp. 127-138.
http://www.math.bas.bg/~epopova/papers/SCAN2000Popova.ps
on a practical example, we have presented our experience in
using Rump's algorithm and a way to sharpen the enclosing intervals
whenever it is necessary.
Evgenija D. Popova
---------------------------------------------------------
Institute of Mathematics & Informatics
Bulgarian Academy of Sciences
Acad. G. Bonchev str., block 8
BG-1113 Sofia, Bulgaria
Phone: (+359 2) 979-3704
Fax: (+359 2) 971-3649
http://www.math.bas.bg/~epopova
---------------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 22 06:38:54 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2MCcr209767
for reliable_computing-outgoing; Fri, 22 Mar 2002 06:38:53 -0600 (CST)
Received: from rztsun.rz.tu-harburg.de (rztsun.rz.tu-harburg.de [134.28.200.14])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2MCcmr09763
for ; Fri, 22 Mar 2002 06:38:49 -0600 (CST)
Received: from gamma.ti3.tu-harburg.de (gamma.ti3.tu-harburg.de [134.28.20.71])
by rztsun.rz.tu-harburg.de (8.9.0/8.8.8) with ESMTP id NAA23543
for ; Fri, 22 Mar 2002 13:38:47 +0100 (MET)
Received: (from jansson@localhost) by gamma.ti3.tu-harburg.de (AIX4.2/UCB 8.7/8.7) id NAA30206 for reliable_computing [at] interval [dot] louisiana.edu; Fri, 22 Mar 2002 13:43:36 +0100 (NFT)
Date: Fri, 22 Mar 2002 13:43:36 +0100 (NFT)
From: "PD Dr. Christian Jansson"
Message-Id: <200203221243.NAA30206 [at] gamma [dot] ti3.tu-harburg.de>
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Interval Linear Systems
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-MD5: DOfwjgT6GWSa8f0nu6yjRA==
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g2MCcnr09764
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear Colleagues,
Arnold Neumaier asked to summarize some of the results of the joint
paper with Jiri Rohn:
C. Jansson and J. Rohn. An Algorithm for
Checking Regularity of Interval Matrices.
SIAM J. Matrix Anal. Appl., 20(3):756-776, 1999.
Checking regularity and singularity of interval
matrices is a known NP-hard problem. This paper presents an algorithm
for checking regularity/singularity of interval matrices. There are
no assumptions on the diameter of the intervals, i.e. it is an exact method
which checks in each case regularity or singularity. The problem of checking
regularity naturally arises in solving linear interval systems, but it
is also important in applications since some frequently used properties
of interval matrices (such as positive defineteness, stability, or the
P-matrix property) can be verified via checking regularity.
Because of the
NP-hardness the algorithm behaves in the worst case exponentially.
However, in many cases the computational work is reasonable. In
our numerical experiments we have considered linear interval
systems of large diameter up to size n=50.
A paper which is more related to the computation of exact
bounds for linear interval systems is:
C. Jansson. Calculation of Exact Bounds
for the Solution Set of Linear Interval
Systems. Linear Algebra and its
Applications 251, 251:321-340, 1997.
This paper presents some topological and graphtheoretical properties of
the solution set of linear algebraic systems with
interval coefficients. Based on these properties, an exact method is given
which, in a finite number of steps, either calculates exact bounds for
each component of the solution set, or finds a singular matrix within
the interval coefficients. The
calculation of exact bounds of the solution set is known to be NP-hard.
This method
needs p calls of a polynomial-time algorithm, where p is the number
of nonempty intersections of the solution set with the orthants. Frequently,
due to physical or economical requirements, many variables do not change the
sign. In those cases p is small, and the method works efficiently.
In both papers it is assumed that the input data vary independently
between given upper and lower bounds, and
data dependencies are not considered.
Concerning dependent input data the following two articles
may be of interest:
C. Jansson. Interval Linear Systems with Symmetric Matrices,
Skew-Symmetric Matrices, and Dependencies in the Right Hand
Side. Computing 47, 265-274, 1991
This article considers an algorithm for computing bounds
of the solution set corresponding to the linear interval system
with the above mentioned special data dependencies. The bounds are not
necessarily exact or optimal. However, The quality of the
bounds can be reliable estimated by computing also
so-called inner inclusions. The general case
of affine-linear data dependencies is presented in
S.M. Rump. Verification Methods for
Dense and Sparse Systems of Equations.
In J. Herzberger, editor, Topics in
Validated Computations --- Studies in
Computational Mathematics, pages 63-136,
Elsevier, Amsterdam, 1994
The solution set of linear interval systems
has a complicated structure. There are some very interesting
papers of Alefeld, Kreinovich, and Mayer which consider these
structures in the case of data dependencies.
Best wishes,
Christian
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 22 08:45:20 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2MEjJl10077
for reliable_computing-outgoing; Fri, 22 Mar 2002 08:45:19 -0600 (CST)
Received: from rztsun.rz.tu-harburg.de (rztsun.rz.tu-harburg.de [134.28.200.14])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2MEjEr10073
for ; Fri, 22 Mar 2002 08:45:15 -0600 (CST)
Received: from gamma.ti3.tu-harburg.de (gamma.ti3.tu-harburg.de [134.28.20.71])
by rztsun.rz.tu-harburg.de (8.9.0/8.8.8) with ESMTP id PAA02586
for ; Fri, 22 Mar 2002 15:45:08 +0100 (MET)
Received: (from jansson@localhost) by gamma.ti3.tu-harburg.de (AIX4.2/UCB 8.7/8.7) id PAA29256 for reliable_computing [at] interval [dot] louisiana.edu; Fri, 22 Mar 2002 15:49:58 +0100 (NFT)
Date: Fri, 22 Mar 2002 15:49:58 +0100 (NFT)
From: Jansson
Message-Id: <200203221449.PAA29256 [at] gamma [dot] ti3.tu-harburg.de>
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Interval Linear Systems
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-MD5: wdgrrO2y5av+Wm9dV6GuaA==
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear Colleagues,
one additional remark to my previous e-mail.
In the case where the intervals are narrow and we have nonlinear
interval data dependencies, these dependencies can be enclosed
very well by using a mean value or centered form. This leads to
a linear interval system with affine-linear dependencies and the
results of the previously mentioned paper of Rump
S.M. Rump. Verification Methods for
Dense and Sparse Systems of Equations.
In J. Herzberger, editor, Topics in
Validated Computations --- Studies in
Computational Mathematics, pages 63-136,
Elsevier, Amsterdam, 1994
can be applied. Then the error bounds are rigorous.
Best wishes,
Christian
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 22 10:18:12 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2MGIBf10310
for reliable_computing-outgoing; Fri, 22 Mar 2002 10:18:11 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2MGI1r10306
for ; Fri, 22 Mar 2002 10:18:02 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g2MGHs1r027160;
Fri, 22 Mar 2002 17:17:55 +0100
Message-ID: <3C9B5932.6C2B937A [at] univie [dot] ac.at>
Date: Fri, 22 Mar 2002 17:17:54 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-21 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: "PD Dr. Christian Jansson"
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Interval Linear Systems
References: <200203221243.NAA30206 [at] gamma [dot] ti3.tu-harburg.de>
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Jansson wrote:
> In the case where the intervals are narrow and we have nonlinear
> interval data dependencies, these dependencies can be enclosed
> very well by using a mean value or centered form. This leads to
> a linear interval system with affine-linear dependencies and the
> results of the previously mentioned paper of Rump
>
> S.M. Rump. Verification Methods for
> Dense and Sparse Systems of Equations.
> In J. Herzberger, editor, Topics in
> Validated Computations --- Studies in
> Computational Mathematics, pages 63-136,
> Elsevier, Amsterdam, 1994
>
> can be applied. Then the error bounds are rigorous.
Moreover, if one uses centered forms with centers at all points
determined by Pownuk's semirigorous approach, and slopes in
place of derivatives, and intersects all intervals obtained in
this way, then one gets not only rigorous error bounds but
also bounds that are optimal or close to optimal in the
case of narrow input.
And from Theorem 2.3.3 of my book, or from interval evaluations
at these points, one can also obtain inner enclosures, so that
the overestimation can be assessed with high quality.
I hope Andrzej Pownuk will write a nice paper along these lines,
with interesting examples from finite element analysis.
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri Mar 22 12:10:16 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2MIAGj10586
for reliable_computing-outgoing; Fri, 22 Mar 2002 12:10:16 -0600 (CST)
Received: from zeus.polsl.gliwice.pl (root [at] zeus [dot] polsl.gliwice.pl [157.158.1.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2MIAAr10581
for ; Fri, 22 Mar 2002 12:10:10 -0600 (CST)
Received: from andrzej1 (a18.asystent.polsl.gliwice.pl [157.158.187.18])
by zeus.polsl.gliwice.pl (8.9.3 (PHNE_25183)/8.9.3) with SMTP id TAA03253;
Fri, 22 Mar 2002 19:10:06 +0100 (MET)
Message-ID: <011b01c1d1cc$d073ad20$0200a8c0@andrzej1>
From: "Andrzej Pownuk"
To: ,
"Arnold Neumaier"
Cc: "Andrzej Pownuk"
References: +ADw-200203221243.NAA30206+AEA-gamma.ti3.tu-harburg.de+AD4- +ADw-3C9B5932.6C2B937A+AEA-univie.ac.at+AD4-
Subject: Re: Interval Linear Systems
Date: Fri, 22 Mar 2002 19:10:12 +0100
MIME-Version: 1.0
Content-Type: text/plain;
charset="UTF-7"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Thank you very much for very useful information.
I apologize once again for my error.
I try to apply all these comments in my future works.
I work for the Department of Civil Engineering.
I am interested in modeling of structures with uncertain parameters.
In my work I usually use finite element method (FEM)
(boundary element method (BEM), finite difference method (FDM) etc.).
to obtain the solution of partial differential equations.
These method lead
to the very large systems of linear equations
(thousands or even million degree of freedom).
To modeling of uncertain parameters we can apply
interval numbers (or interval valued random variables).
In this situations we have system of thousands equations
with interval parameters in the following form:
K(h)u+AD0-Q(h) where h belong to +AFs-h+AF0-
where h is a vector of uncertain parameters.
These are usually parameter dependent system of equations.
(I don't know (direct) practical applications of
system of linear interval equations
with independent coefficients in computational mechanics)
There are many methods of solution of the system
of linear interval equations (with independent coefficients).
Unfortunately due to overestimation problem
they cannot be apply in practical applications.
In may country we have a small team
which work on these topics.
(http://www.ippt.gov.pl/+AH4-zkulpa/quaphys/QAGroup.html)
I know the work of Mr. Jansson,
but I don+IBk-t know any example of application
in computational mechanics which is connected
with his method.
I know the work of Mr Roump and Ms. Popova.
In my country we tested this method.
Unfortunately there are two problems:
1) The dependency of the parameters
in my problems is more complicated
than linear combination of interval parameters.
In the simplest cases we have the following
coefficient of the stiffness matrix:
K(i,j)+AD0-2+ACo-p1+ACo-p2+ACo-p3+-8+ACo-p1+ACo-p3+-5+ACo-p1+ACo-p2+-...+-4+ACo-p3+ACo-p4
where K(i,j) is a coefficient of the matrix K,
p1,p2,p3,p4 are interval parameters.
We can apply linear combination of interval parameters
only in very special cases.
2) I don't know the efficiency of
Rump+IBk-s ( and Popova) method in high dimensional problems.
(1000, 10 000 equations)
In my country Ms Iwona Skalna have tested
only examples with
approximately 20 degree of freedom.
Mr Muhanna in the paper
Muhanna R.L., Mullen R.L.,
Uncertainty in Mechanics
Problems - Interval - Based Approach.
Journal of Engineering Mechanics, Vol.127, No.6, 2001, 557-556,
have solved problems with about 20 degree of freedom
and one interval parameter.
What happened when we will have thousand equations?
I think that this topic need more investigation.
( or I have to read something (????) )
I know that my method
or other method which are based on sensitivity analysis
gives only approximate solution but they has three advantages:
(in my Ph.D. dissertation I investigated some other method.)
1) Can be applied to very high dimensional problems.
2) Unsung this method we can take into account
very complicated cases of dependency of the interval parameters.
3) These methods can be applied for nonlinear problems
(even dynamics).
Additionally as far as I know
most of practical method of computation gives only approximate results.
(but I understood that this is not the topic of this mailing list.)
The problem is how accurate results we can calculate.
I met a lot of person
which are very interested in
practical (commercial) applications
of the problems, which I described above.
Thank you very much for all comments,
Regards,
Andrzej Pownuk
+AD4-
+AD4- Jansson wrote:
+AD4-
+AD4- +AD4- In the case where the intervals are narrow and we have nonlinear
+AD4- +AD4- interval data dependencies, these dependencies can be enclosed
+AD4- +AD4- very well by using a mean value or centered form. This leads to
+AD4- +AD4- a linear interval system with affine-linear dependencies and the
+AD4- +AD4- results of the previously mentioned paper of Rump
+AD4- +AD4-
+AD4- +AD4- S.M. Rump. Verification Methods for
+AD4- +AD4- Dense and Sparse Systems of Equations.
+AD4- +AD4- In J. Herzberger, editor, Topics in
+AD4- +AD4- Validated Computations --- Studies in
+AD4- +AD4- Computational Mathematics, pages 63-136,
+AD4- +AD4- Elsevier, Amsterdam, 1994
+AD4- +AD4-
+AD4- +AD4- can be applied. Then the error bounds are rigorous.
+AD4-
+AD4- Moreover, if one uses centered forms with centers at all points
+AD4- determined by Pownuk's semirigorous approach, and slopes in
+AD4- place of derivatives, and intersects all intervals obtained in
+AD4- this way, then one gets not only rigorous error bounds but
+AD4- also bounds that are optimal or close to optimal in the
+AD4- case of narrow input.
+AD4-
+AD4- And from Theorem 2.3.3 of my book, or from interval evaluations
+AD4- at these points, one can also obtain inner enclosures, so that
+AD4- the overestimation can be assessed with high quality.
+AD4-
+AD4- I hope Andrzej Pownuk will write a nice paper along these lines,
+AD4- with interesting examples from finite element analysis.
+AD4-
+AD4-
+AD4- Arnold Neumaier
+AD4-
From owner-reliable_computing [at] interval [dot] louisiana.edu Sat Mar 23 03:00:42 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2N90fe12123
for reliable_computing-outgoing; Sat, 23 Mar 2002 03:00:41 -0600 (CST)
Received: from suntana.fh-konstanz.de (suntana.fh-konstanz.de [141.37.9.230])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2N90Tr12119
for ; Sat, 23 Mar 2002 03:00:29 -0600 (CST)
Received: from fh-konstanz.de (dialup60.fh-konstanz.de [141.37.217.60])
by suntana.fh-konstanz.de (8.9.3+Sun/8.9.3) with ESMTP id JAA03259
for ; Sat, 23 Mar 2002 09:58:01 +0100 (MET)
Message-ID: <3C9C470A.64CE4ED1@fh-konstanz.de>
Date: Sat, 23 Mar 2002 10:12:42 +0100
From: Garloff [at] suntana [dot] fh-konstanz.de,
=?iso-8859-1?Q?J=FCrgen?=
Organization: Fachhochschule Konstanz
X-Mailer: Mozilla 4.51 [en] (Win98; I)
X-Accept-Language: en
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Taylor models - how to get valid comparisons
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Dear Arnold,
I am late but I want to comment on your remarks:
> One correction:
> You state that the Bernstein form gives exact results for sufficiently
> small boxes. But this is true only if the extremal value is attained in
> a box; it is not the case, e.g., for f(x)=x^3-6x in [0,2] since the
> minimum
> is irrational.
The precise statement (for simplicity stated here in the 1D case) is
that Bernstein expansion over a fixed interval, [a,b] say, gives the
exact range on [a, a + eps] and [b - eps,b] for eps sufficiently small.
This result can be found in the dissertation by Volker Stahl (Interval
Methods for Bounding the Range of Polynomials and Solving Systems of
Nonlinear Eqs., RISC, University of Linz, 1995) which contains also a
lot of experimental comparisons in the univariate case of the Bernstein
form with other forms, e.g., slope interpolation form and parabolic
boundary value form.
I'd also recommend that you mention the leading order of
> the
> cost of the transformation to Bernstein form, since this may explain the
> limitations of your method in higher dimensions.
>
This transformation can be accomplished e.g. by the Horner scheme (in
the multivariate case possibly in parallel)- alternatively by de
Casteljau's algorithm. If subdivision is applied, this transformation
has to be performed only at the beginning.
Best wishes,
Juergen
From owner-reliable_computing [at] interval [dot] louisiana.edu Sat Mar 23 06:33:44 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2NCXhT12795
for reliable_computing-outgoing; Sat, 23 Mar 2002 06:33:43 -0600 (CST)
Received: from mail.comset.net (mail.comset.net [213.172.0.3])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2NCXbr12791
for ; Sat, 23 Mar 2002 06:33:38 -0600 (CST)
Received: from 9-136.dialup.comset.net ([213.172.9.136] helo=e0gumi46)
by mail.comset.net with smtp (Exim 3.33 #1)
id 16okjF-0004hc-00
for reliable_computing [at] interval [dot] louisiana.edu; Sat, 23 Mar 2002 15:34:38 +0300
Message-ID: <00df01c1d266$6027c200$710bfea9 [at] wplus [dot] net>
From: "Vyacheslav Nesterov"
To: "RC mailing list"
Subject: Email address of Reliable Computing will be changed tomorrow
Date: Sat, 23 Mar 2002 15:28:24 +0300
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_00DC_01C1D27F.5F493F80"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2615.200
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
This is a multi-part message in MIME format.
------=_NextPart_000_00DC_01C1D27F.5F493F80
Content-Type: text/plain;
charset="koi8-r"
Content-Transfer-Encoding: quoted-printable
Dear Colleagues,
This message is to inform you that my address and=20
official address of Reliable Computing journal changes tomorrow
from
slavanest [at] yahoo [dot] com
to=20
slnest [at] comset [dot] net
First address will work properly during at least one month and hopefully =
much more,
however please use the new address for all kind of communications with =
me.
Best regards,
Slava Nesterov
------=_NextPart_000_00DC_01C1D27F.5F493F80
Content-Type: text/html;
charset="koi8-r"
Content-Transfer-Encoding: quoted-printable
Dear Colleagues,
This message is to inform you =
that my address=20
and
official address of Reliable =
Computing=20
journal changes tomorrow
from
to
First address will work properly =
during at=20
least one month and hopefully much more,
however please use the new =
address for all=20
kind of communications with me.
Best regards,
Slava =
Nesterov
------=_NextPart_000_00DC_01C1D27F.5F493F80--
From owner-reliable_computing [at] interval [dot] louisiana.edu Sat Mar 23 17:58:28 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2NNwRG13913
for reliable_computing-outgoing; Sat, 23 Mar 2002 17:58:27 -0600 (CST)
Received: from bologna.vision.caltech.edu (bologna.vision.caltech.edu [131.215.134.19])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2NNwMr13909
for ; Sat, 23 Mar 2002 17:58:23 -0600 (CST)
Received: from peking.vision.caltech.edu (peking [131.215.134.18])
by bologna.vision.caltech.edu (8.9.3/8.8.7) with ESMTP id PAA12537
for ; Sat, 23 Mar 2002 15:58:22 -0800
Received: (from arrigo@localhost)
by peking.vision.caltech.edu (8.9.3+Sun/8.9.1) id PAA20200;
Sat, 23 Mar 2002 15:57:46 -0800 (PST)
X-Authentication-Warning: peking.vision.caltech.edu: arrigo set sender to arrigo [at] vision [dot] caltech.edu using -f
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Taylor models - how to get valid comparisons
References: <3C9C470A.64CE4ED1@fh-konstanz.de>
From: Arrigo Benedetti
Date: 23 Mar 2002 15:57:46 -0800
In-Reply-To: <3C9C470A.64CE4ED1@fh-konstanz.de>
Message-ID:
Lines: 34
User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.4
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id g2NNwNr13910
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Garloff [at] suntana [dot] fh-konstanz.de, Jürgen writes:
> Dear Arnold,
> I am late but I want to comment on your remarks:
>
>
> > One correction:
> > You state that the Bernstein form gives exact results for sufficiently
> > small boxes. But this is true only if the extremal value is attained in
> > a box; it is not the case, e.g., for f(x)=x^3-6x in [0,2] since the
> > minimum
> > is irrational.
>
> The precise statement (for simplicity stated here in the 1D case) is
> that Bernstein expansion over a fixed interval, [a,b] say, gives the
> exact range on [a, a + eps] and [b - eps,b] for eps sufficiently small.
> This result can be found in the dissertation by Volker Stahl (Interval
> Methods for Bounding the Range of Polynomials and Solving Systems of
> Nonlinear Eqs., RISC, University of Linz, 1995) which contains also a
> lot of experimental comparisons in the univariate case of the Bernstein
> form with other forms, e.g., slope interpolation form and parabolic
> boundary value form.
>
Just in case anyone is interested, this thesis is available at:
ftp://ftp.risc.uni-linz.ac.at/pub/private/vstahl/thesis.ps
Best,
-Arrigo
--
Dr. Arrigo Benedetti e-mail: arrigo [at] vision [dot] caltech.edu
Caltech, MS 136-93 phone: (626) 644-3757
Pasadena, CA 91125 fax: (626) 795-8649
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Mar 25 06:40:44 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2PCei918093
for reliable_computing-outgoing; Mon, 25 Mar 2002 06:40:44 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2PCebr18089
for ; Mon, 25 Mar 2002 06:40:38 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g2PCeTsg062294;
Mon, 25 Mar 2002 13:40:30 +0100
Message-ID: <3C9F1ABD.5D290ADE [at] univie [dot] ac.at>
Date: Mon, 25 Mar 2002 13:40:29 +0100
From: Arnold Neumaier
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-31 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: Andrzej Pownuk
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: On rigor in reliable computing
References: +ADw-200203221243.NAA30206+AEA-gamma.ti3.tu-harburg.de+AD4- +ADw-3C9B5932.6C2B937A+AEA-univie.ac.at+AD4- <011b01c1d1cc$d073ad20$0200a8c0@andrzej1>
Content-Type: text/plain; charset=UTF-7
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Andrzej Pownuk wrote:
> Additionally as far as I know
> most of practical method of computation gives only approximate results.
> (but I understood that this is not the topic of this mailing list.)
> The problem is how accurate results we can calculate.
I think it is ok to discuss on the list *all* problems with
intervals, and also propose approximation algorithms that are not
rigorous, for problems that currently defy rigorous methods.
Indeed, less rigorous methods may contain the germs for more rigorous
ones, and problems thast can be solved now by less rigorous methods
pose challenges for more rigorous attacks.
But the degree of rigor used should be clearly visible
(and mentioned in papers at prominent places - abstract,
introduction, conclusion).
There are four increasingly demanding stages of rigor:
1. With uncontrolled approximations. For problems involving functions,
this is the realm of traditional numerical analysis, where asymptotic
estimates are all that is available to justify a method.
2. Without uncontrolled approximations but with unverified assumptions.
This is the case e.g. for methods that assume that the intervals are
sufficiently narrow, without giving precise criteria for how narrow is
enough.
3. Without uncontrolled approximations or unverified assumptions,
but without error control. This would be rigorous in
exact arithmetic, but is not in floating point arithmetic.
An example is Gaussian elimination for exact data.
For bounding interval linear systems, Rohn's sign accord
algorithms belongs to this category, since so far no one has
proposed a safe strategy for making the algorithm behave
correctly in floating points.
4. Without uncontrolled approximations or unverified assumptions,
and with rounding error control. These are the only algorithms
that deserve the designation 'rigorous' or 'exact'.
Progress consists in bringing new problems into stage 1, or bringing
older or larger problems than before one stage higher.
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Mar 25 07:57:57 2002
Received: (from daemon@localhost)
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g2PDvuA18299
for reliable_computing-outgoing; Mon, 25 Mar 2002 07:57:56 -0600 (CST)
Received: from marnier.ucs.louisiana.edu (root [at] marnier [dot] ucs.louisiana.edu [130.70.132.233])
by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g2PDvpr18295
for ; Mon, 25 Mar 2002 07:57:52 -0600 (CST)
Received: from liberty (liberty.louisiana.edu [130.70.46.171])
by marnier.ucs.louisiana.edu (8.11.3/8.11.3/ull-ucs-mx-host_1.6) with SMTP id g2PDvT402815;
Mon, 25 Mar 2002 07:57:33 -0600 (CST)
Message-Id: <2.2.32.20020325140521.01536cf4 [at] 130 [dot] 70.132.231>
X-Sender: rbk5287 [at] 130 [dot] 70.132.231
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Mon, 25 Mar 2002 08:05:21 -0600
To: Arnold Neumaier ,
Andrzej Pownuk