From owner-reliable_computing [at] interval [dot] louisiana.edu Mon May 2 10:54:06 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j42Fs6Lr029127
for ; Mon, 2 May 2005 10:54:06 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j42Fs6qw029126
for reliable_computing-outgoing; Mon, 2 May 2005 10:54:06 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j42FrvkX029122
for ; Mon, 2 May 2005 10:54:02 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j42FrBp08699;
Mon, 2 May 2005 09:53:11 -0600 (MDT)
Message-Id: <200505021553.j42FrBp08699 [at] cs [dot] utep.edu>
Date: Mon, 2 May 2005 09:53:09 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: two interval-related tracks for ACM Symposium on Applied Computing
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: rogerw [at] utulsa [dot] edu, vladik [at] cs [dot] utep.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 3X/xkpOdqfG9VWIdHjwGSw==
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
Dear Friends,
We have just been informed that the organizers of the 2006 ACM Symposium on
Applied Computing (Dijon, France, April 23-27, 2006) have approved two
interval-related track proposals:
* Reliable Computations and their Applications, with an emphasis on combining
interval and constraint satisfaction techniques
(the webpage http://www.cs.utep.edu/mceberio/Research/Conferences/RCA06/ is
being set up, please wait a few days until it is finalized)
and
* More Accurate Computations: Methods and Software, with a focus on today's and
tomorrow's methods and software that go father than the precision currently
available on our computers
(organized by Philippe Langlois and Siegfried M. Rump).
Deadline for submitting a paper to the organizers is August 28, 2005.
Please note that the acceptance rate for SAC'06 is set up at 36%, so only (at
most) best 36% of the submitted papers will be accepted for oral presentation.
Please do not hesitate to submit multiple papers; exact submission rules will
be posted on the SAC'06 webpage.
Martine and Vladik
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed May 4 12:34:14 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44HYEKn004005
for ; Wed, 4 May 2005 12:34:14 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44HYEmD004004
for reliable_computing-outgoing; Wed, 4 May 2005 12:34:14 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44HY5LV004000
for ; Wed, 4 May 2005 12:34:11 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j44HXGj24620;
Wed, 4 May 2005 11:33:16 -0600 (MDT)
Message-Id: <200505041733.j44HXGj24620 [at] cs [dot] utep.edu>
Date: Wed, 4 May 2005 11:33:15 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: report on interval talks at SAC'05
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: mceberio [at] cs [dot] utep.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: T6X2KRAViaqiQx47DYBdZw==
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
Reliable Computations and their Applications (RCA)
(with an emphasis on combining interval and
constraint satisfaction techniques)
a Technical Track at
the 20th ACM Symposium on Applied Computing SAC'2005
(March 13 - 17, 2005, Santa Fe, New Mexico, USA)
SAC'05
For the past twenty years, the ACM Symposium on Applied
Computing has been a primary gathering forum for applied
computer scientists, computer engineers, software engineers,
and application developers from around the world.
RCA TRACK: MOTIVATIONS
Many numerical computations, be they solutions to systems of
differential equations or optimization problems coming from applied
areas like protein folding, do not provide us with guaranteed
computation results. In many situations, we have numerical solutions,
we may even have a theorem guaranteeing that eventually, this numerical
solution tends to the actual precise one, but the algorithm itself
does not provide us with guaranteed bounds on the difference between the
numerical approximate solution and the desired actual one.
Therefore, in some practical situations, numerical solutions
are much farther from the actual (unknown) precise
solutions than the users assume. As a result, we often end up with
inefficient local maxima for practical optimization problems like
chemical engineering - or even with a mission failure if we are
planning, e.g., a spaceship trajectory.
For some such algorithms, researchers have found guaranteed bounds, but
producing a guaranteed bound for each algorithm requires a lot of work.
It is therefore desirable to develop a methodology that would provide
algorithms with automatic result verification, i.e., with
automatically generated upper bound on the difference between the
actual and the numerical solution. In other words, we need computation
techniques that produce reliable (guaranteed) results.
This problem was recognized already in the late 1950s when Lockheed
wanted to develop algorithmic techniques guaranteeing
trajectories of spaceflights. These techniques, largely developed
by Ramon E. Moore, were later applied to other
practical problems where deviations from the target are of critical
importance. The main idea behind these techniques is that
at any intermediate step of the computations, instead of the exact
number, we keep an interval of possible values. For inputs (that
usually come from measurements), we have an interval because
measurements are never 100% accurate; if the manufacturer of the
measuring instrument guarantees that the measurement error is D or
smaller, then the measuring result X means that the actual value is in
the interval [X-D,X+D]. At each elementary computational step, we
apply interval arithmetic to the corresponding intervals and produce
the interval for the result; e.g., [a,b]+[c,d] leads to [a+c,b+d].
Of course, this "straightforward interval computation", that does not
take dependence between intermediate results into consideration, does
not always lead to efficient estimates; however, in the last 40+
years, efficient interval computations methods have been developed
based on this original idea. There are a lot of interesting
applications of interval computations, there is a lot of potential,
but there are still numerous open problems, situations where new
techniques are needed.
One such technique that has also been used to provide guaranteed
bounds is the technique of constraint propagation. This technique
originated in logical AI problems, and it has been lately successfully
applied to numerical problems, often in conjunction with interval
methods. For example, one of the latest textbooks on interval
computations, by Jaulin et al., contains robot-related practical
examples of combining these two techniques. This combination has
started, it is the object of interest by many researchers, it has
already led to interesting and efficient packages like Numerica, but
there is still a lot of room for potential improvement.
The main objective of this track was to encourage such collaboration
by bringing together not only algorithm developers but also
practitioners whose practical needs can help to guide researchers
in the proper directions.
PAPERS PRESENTED AT THE TRACK
The opening technical talk was given by Professor Ramon E. Moore. This
talk supplemented a well-received keynote talk that Professor Moore
gave on the importance of taking interval uncertainty into account.
In his track talk, "Order Relations and Rigor in
Computing", he emphasized that while there are
many efficient techniques for transforming a non-branching algorithm
into an algorithm that properly takes into account the interval
uncertainty of the inputs and the interval uncertainty caused by
round-off errors, it is much more difficult to properly
deal with the order-related branching (like "if a>0 then ... else
...") under interval uncertainty.
The ultimate goal of interval and constraint techniques -- the goal
emphasized in the Symposium -- is to use these techniques in real-life
applications. For these applications to be possible, it is often
necessary to make the techniques more efficient. The first two talks
presented at the track described two approaches towards this
efficiency.
Frederic Goualard from Laboratoire d'Informatique LINA
(Nantes, France) presented a paper
"On Considering an Interval Constraint Solving Algorithm as a
Free-Steering Nonlinear Gauss-Seidel Procedure",
on interval methods for constraint solving. In such method, we usually
start by designing, for each constraint fk(x1,...,xn)=0, algorithms
that use the known intervals for all the variables except for one of
them (xi) into the corresponding interval for xi. These algorithms
come, e.g., from transforming the constraint into the form
xi=f_{ki}(x1,...,x_{i-1},x_{i+1},...,xn) and then
applying interval techniques to the resulting expression.
The traditional constraint satisfaction approach then consists of
sequentially applying the resulting algorithms in some order to
reduce the width of the intervals for xi.
Goualard has shown that after we used the
k-th constraint to reduce the width of i-th interval xi, it may be
better not to use the same constraint to reduce other
algorithms; as a result, for each constraint, we select a single
variable whose interval width we want to decrease.
Goualard has also shown that a different way of selecting a variable
can lead to a drastic speed up of the resulting
algorithm. He also found a heuristic that works the best.
When the interval widths stop decreasing, then, traditionally, we
bisect the resulting box, and continue iterations with the
resulting half-boxes. The bisection step is necessary, because, e.g.,
for a constraint x^2=4, the smallest interval containing both solution
is the interval [-2,2]; so, if we want to narrow down the resulting
algorithm, we have to bisect it into two halves [-2,0] and [0,2] -- and
then use the same constraint to converge to the answers -2 and 2.
In this example, it is clear that we can speed up computations if we
represent the result of applying the constraint x^2=4 not as an
interval, but as a union of two intervals -- in this case, as the
union of two degenerate intervals [-2,-2] and [2,2].
In their paper "Box-Set Consistency for Interval-Based Constraint
Problems", Gilles Chabert, Gilles Trombettoni and Bertrand Neveu
(Project CORPIN, France) modified the constraint techniques so as to
allow unions of intervals on each step, and showed that for many
realistic constraints, this modification indeed leads to a drastic
speed-up.
When designing efficient algorithms, it is desirable to know
beforehand what can be achieved and what cannot, so that we do not
waste time trying to develop algorithm for a class of problem that is
so wide that no efficient algorithm is possible for this class. One
such "too wide" class was described in a paper
"Computing the Cube of an Interval Matrix is
NP-Hard" by Olga Kosheleva, Vladik Kreinovich (University of Texas at El
Paso, USA), Guenter Mayer (University of Rostock, Germany), and Hung
T. Nguyen (New Mexico State University, USA).
This paper deals with the fact that
sometimes, additional constraints come from the fact that one of the
intermediate quantities comes from previous computations. For example,
in the first approximation, the transition from a state of the system
at a moment t to a state at the next moment of time can be described
by a linear formula s'=As for some matrix A. To describe the k-step
evolution, we therefore need to compute k-th power of the
corresponding matrix A. Since in practice, we only know A with
interval uncertainty, we thus need to be able to compute the power of a
given interval matrix.
It seems reasonable to compute this power just like we compute the
power of an exactly known matrix - by multiplying A by itself several
times. For the square, it is possible to provide the exact interval
enclosure. However, when after computing an interval enclosure B for A^2,
we compute A^3 as B*A, we get an excess width -- because we ignored the
additional constraint that the actual matrix A^2 has to be a square of
one of the matrices from the original interval matrix. It turns out
that taking this constraint into account is computationally expensive
(in general, NP-hard).
An interesting new application of interval techniques
was described in a paper "Enhancing Network Intrusion Detection Systems with
Interval Methods" by Qiang Duan, Chenyi Hu, and Han-Chieh Wei
(University of Central Arkansas, USA).
Network intrusions are usually detected because they lead to
unusual behavior, i.e., in mathematical terms, to unusual temporal
sequences of states. There exist numerical characteristics that
reflect the behavior, and the difference between acceptable and
suspicious behavior is usually described by a threshold. However,
there is a problem with this approach: if the threshold is set up too
high, we may let intruders in; if the threshold is too low, we get too
many false alarms. The authors show that since a lot of the data and
rules are heuristic anyway, it does not make too much sense to process
exact values, it is much more reasonable to represent the
corresponding uncertainty by intervals and process the corresponding
intervals. As a result, not only we get a faster algorithm (since
there is no need for computations to be more accurate than the
original uncertainty), but we can also
decrease the number of false alarms -- because now, for each
quantity, we have two numerical values (interval bounds) instead of
one, so setting different thresholds for these two values gives us
more flexibility in distinguishing between intrusions and normal
behavior.
INTERVAL-RELATED TALKS PRESENTED AT OTHER TRACKS
Several interval-related papers were presented at other tracks, in
particular, at the Constraint Solving and Programming (CSP) track. We
will give three examples.
In their paper "Controlled Propagation in Continuous Numerical Constraint
Networks", Frederic Goualard and Laurent Granvilliers (LINA,
France) deal with the fact that difficult-to-handle numerical
constraints
fk(x1,..,xn)=0 are usually replaced -- interval-computations style --
with a series of simpler constraints reflecting intermediate steps in
computing the expression fk(x1,...,xn). As a result of this
replacement, we get set a large of constraints, which leads to longer
computation time. Sometimes, some of the resulting simple constraints
follow from the others and are, therefore, redundant. It turns out
that if we take this dependence between constraints into account, we
can often significantly decrease the resulting computation time.
Another speed-up idea was described by Roman Bartak (Charles
University, Czech Republic) and Hana Rudova (Masaryk University, Czech
Republic) in their paper "Limited Assignments: a New Cutoff Strategy
for Incomplete Depth-First Search". Often, if we use the same
constraint again and again instead of the others (or bisect one of the
intervals much more times that others), this is a sign that maybe we
need a change in strategy. The authors recommend to set up a limit on
the number of times each variable (or each constraint) can be handles,
and to change strategy if we reach this limit for one of the variables
(or one of the constraints).
Several interval-related papers dealt with practical applications.
For example,
in their paper "Efficient mass decomposition", Sebastian Bocker and
Zsuzsanna Liptak explore the fact that molecular weights, while
approximately integers, are not exactly integers. As a result,
if we know the exact value of the molecular weight M of a protein (as
measured, e.g., by a mass-spectrometer), then, just from this number,
we can often tell how many aminoacids ai of different types form this
protein (i.e., for which M = sum ai*mi, where mi are masses of these
aminoacids). The authors provide efficient algorithms that take into
account interval uncertainties in measuring the masses M and mi.
CONFERENCE VENUE
Located at 7000 feet (2000 m) in the foothills of Rocky Mountains,
Santa Fe, New Mexico, the "City Different", is the oldest capital city
in the United States, the city that has a long history and rich
cultural heritage. Originally a small town populated by Pueblo Indians,
it became a capital of Nueva Espana (New Spain) in 1607, then a
capital of the Mexican state of Nuevo Mexico (New Mexico);
since 1840s, it is part of the USA. Santa Fe is famous for its
culture, art, and traditions.
The conference started on a warm (almost summer) day, but the next
day, an unexpected heavy snowstorm blocked all the roads leading in
and out of Santa Fe, so those who planned to leave early had to stay a
few extra days. We did not regret it because the organizers did a
truly great job: a wonderful reception with Native
American dancers and storytellers was followed by a multi-cultural
dinner, after which dance instructors taught us the art of Country
Western Dancing.
Next conference will be in Dijon, France, in Dijon, April 23-27,
2006. See y'all there!
Martine Ceberio, Vladik Kreinovich
University of Texas at El Paso
mceberio [at] cs [dot] utep.edu vladik [at] cs [dot] utep.edu
Michel Rueher
Universite de Nice ESSI, Sophia Antipolis, France
rueher [at] essi [dot] fr
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed May 4 15:40:57 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44Kev7v004171
for ; Wed, 4 May 2005 15:40:57 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44KevHw004170
for reliable_computing-outgoing; Wed, 4 May 2005 15:40:57 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44KemFn004166
for ; Wed, 4 May 2005 15:40:54 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j44Ke1U25944
for ; Wed, 4 May 2005 14:40:01 -0600 (MDT)
Message-Id: <200505042040.j44Ke1U25944 [at] cs [dot] utep.edu>
Date: Wed, 4 May 2005 14:40:00 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: IEEE 754 standard is being revised
To: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: zrL+iDBciTZM2tuKOd3A4w==
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
The latest May 2005 issue of IEEE Computer has a short article by William Kahan
and Dan Zuras from the IEEE 754 revision committee. Some of the issues they
raise, e.g., the effect of round-off errors on the computational results, are
very relevant to us.
IEEE is a very important source of standards for computer design and use, so
their decisions are of extreme importance to us.
Maybe someone can clarify the situation to the mailing list - if our viewpoint
is already being promoted great. If not sufficiently, maybe there is something
we as a community can do.
Vladik
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed May 4 16:36:02 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44La1j6004276
for ; Wed, 4 May 2005 16:36:01 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44La14G004275
for reliable_computing-outgoing; Wed, 4 May 2005 16:36:01 -0500 (CDT)
Received: from marnier.ucs.louisiana.edu (root [at] marnier [dot] ucs.louisiana.edu [130.70.132.233])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44LZrtd004271
for ; Wed, 4 May 2005 16:35:58 -0500 (CDT)
Received: from Liberty (h158065.louisiana.edu [130.70.158.65])
by marnier.ucs.louisiana.edu (8.13.1/8.13.1/ull-ucs-mx-host_1.9) with SMTP id j44LZ7sB000055
for ; Wed, 4 May 2005 16:35:12 -0500 (CDT)
Message-Id: <2.2.32.20050504213308.00b893e8 [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: Wed, 04 May 2005 16:33:08 -0500
To: reliable_computing [at] interval [dot] louisiana.edu
From: "R. Baker Kearfott"
Subject: Re: IEEE 754 standard is being revised
X-Virus-Scanned: ClamAV 0.82/861/Sat Apr 30 04:28:52 2005 on marnier.ucs.louisiana.edu
X-Virus-Status: Clean
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Esteemed colleagues,
In case you don't already know, Bill Kahan, a major player in
creation and adoption of the original IEEE 754 standard, is also
a relatively early pioneer in interval arithmetic; Bill can also
be considered the originator of extended interval arithmetic (for
the system to be closed under division by intervals containing 0).
In fact, IEEE 754 was at least partially designed with interval
arithmetic in mind. The last time I talked with Bill (also known
as "Velvel") Kahan, about 10 years ago, he was still a strong friend
of interval arithmetic.
In any case, I encourage people to investigate the present activity
and to become involved. Hopefully Bill has a similar viewpoint and
as much energy as he did when he worked on the original standard.
It will be interesting to see what items are thought to need changing.
Best regards,
Baker
At 02:40 PM 5/4/2005 -0600, Vladik Kreinovich wrote:
>
>The latest May 2005 issue of IEEE Computer has a short article by William
Kahan
>and Dan Zuras from the IEEE 754 revision committee. Some of the issues they
>raise, e.g., the effect of round-off errors on the computational results, are
>very relevant to us.
>
>IEEE is a very important source of standards for computer design and use, so
>their decisions are of extreme importance to us.
>
>Maybe someone can clarify the situation to the mailing list - if our viewpoint
>is already being promoted great. If not sufficiently, maybe there is something
>we as a community can do.
>
>Vladik
>
>
>
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed May 4 16:38:27 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44LcRXB004284
for ; Wed, 4 May 2005 16:38:27 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44LcQex004283
for reliable_computing-outgoing; Wed, 4 May 2005 16:38:26 -0500 (CDT)
Received: from sunshine.math.utah.edu (IDENT:j9XeS62o9PW792CqXsbOpsgrC6336Kut [at] sunshine [dot] math.utah.edu [128.110.198.2])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44LcIx2004279
for ; Wed, 4 May 2005 16:38:24 -0500 (CDT)
Received: from psi.math.utah.edu (IDENT:+Z2croVIr5jY556W+/elnpEyh5Gnl1aP [at] psi [dot] math.utah.edu [155.101.96.19])
by sunshine.math.utah.edu (8.13.3/8.13.3) with ESMTP id j44LbNjO007341;
Wed, 4 May 2005 15:37:23 -0600 (MDT)
Received: from psi.math.utah.edu (IDENT:ObnrLlzUyOWb8bH8m9Wq3/SgpP8o0lsj@localhost [127.0.0.1])
by psi.math.utah.edu (8.12.11/8.12.10) with ESMTP id j44LbNBM012917;
Wed, 4 May 2005 15:37:23 -0600 (MDT)
Received: (from beebe@localhost)
by psi.math.utah.edu (8.12.11/8.12.10/Submit) id j44LbNTY012916;
Wed, 4 May 2005 15:37:23 -0600 (MDT)
Date: Wed, 4 May 2005 15:37:23 -0600 (MDT)
From: "Nelson H. F. Beebe"
To: reliable_computing [at] interval [dot] louisiana.edu
Cc: beebe [at] math [dot] utah.edu
X-US-Mail: "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: IEEE 754 standard is being revised
Message-ID:
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0b5 (sunshine.math.utah.edu [128.110.198.2]); Wed, 04 May 2005 15:37:23 -0600 (MDT)
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Thanks to Vladik for pointing out the new article in IEEE Computer; my
issue arrived yesterday, but I had not opened it yet.
Here is a BibTeX entry with URLs that will be accessible to list
members with institutional or personal access to the online IEEE
journals:
@String{j-COMPUTER = "Computer"}
@Article{Kahan:2005:OQD,
author = "William Kahan and Dan Zuras",
title = "An Open Question to Developers of Numerical Software",
journal = j-COMPUTER,
volume = "38",
number = "5",
pages = "91--94",
month = may,
year = "2005",
CODEN = "CPTRB4",
ISSN = "0018-9162",
bibdate = "Wed May 04 15:33:06 2005",
URL = "http://csdl.computer.org/comp/mags/co/2005/05/r5toc.htm;
http://csdl.computer.org/comp/mags/co/2005/05/r5091abs.htm;
http://csdl.computer.org/dl/mags/co/2005/05/r5091.pdf",
acknowledgement = ack-nhfb,
}
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- University of Utah FAX: +1 801 581 4148 -
- Department of Mathematics, 110 LCB Internet e-mail: beebe [at] math [dot] utah.edu -
- 155 S 1400 E RM 233 beebe [at] acm [dot] org beebe [at] computer [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 Wed May 4 17:26:27 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44MQRsL004382
for ; Wed, 4 May 2005 17:26:27 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44MQRTs004381
for reliable_computing-outgoing; Wed, 4 May 2005 17:26:27 -0500 (CDT)
Received: from ms-smtp-02-eri0.ohiordc.rr.com (ms-smtp-02-smtplb.ohiordc.rr.com [65.24.5.136])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44MQIQt004377
for ; Wed, 4 May 2005 17:26:23 -0500 (CDT)
Received: from Moore (cpe-204-210-226-111.columbus.res.rr.com [204.210.226.111])
by ms-smtp-02-eri0.ohiordc.rr.com (8.12.10/8.12.7) with SMTP id j44MPMXX022860;
Wed, 4 May 2005 18:25:24 -0400 (EDT)
Message-ID: <006301c550f8$4462e310$1702a8c0@Moore>
From: "Ray Moore"
To: "Vladik Kreinovich" ,
References: <200505042040.j44Ke1U25944 [at] cs [dot] utep.edu>
Subject: Re: IEEE 754 standard is being revised
Date: Wed, 4 May 2005 18:26:07 -0400
MIME-Version: 1.0
Content-Type: text/plain;
format=flowed;
charset="iso-8859-1";
reply-type=original
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2900.2180
X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
X-Virus-Scanned: Symantec AntiVirus Scan Engine
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
See http://grouper.ieee.org/groups/754/revision.html
----- Original Message -----
From: "Vladik Kreinovich"
To:
Sent: Wednesday, May 04, 2005 4:40 PM
Subject: IEEE 754 standard is being revised
>
> The latest May 2005 issue of IEEE Computer has a short article by William
> Kahan
> and Dan Zuras from the IEEE 754 revision committee. Some of the issues
> they
> raise, e.g., the effect of round-off errors on the computational results,
> are
> very relevant to us.
>
> IEEE is a very important source of standards for computer design and use,
> so
> their decisions are of extreme importance to us.
>
> Maybe someone can clarify the situation to the mailing list - if our
> viewpoint
> is already being promoted great. If not sufficiently, maybe there is
> something
> we as a community can do.
>
> Vladik
>
>
>
From owner-reliable_computing [at] interval [dot] louisiana.edu Wed May 4 18:51:49 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44NpnPJ004545
for ; Wed, 4 May 2005 18:51:49 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j44NpnbL004544
for reliable_computing-outgoing; Wed, 4 May 2005 18:51:49 -0500 (CDT)
Received: from orsfmr003.jf.intel.com (fmr18.intel.com [134.134.136.17])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j44NpckG004540
for ; Wed, 4 May 2005 18:51:45 -0500 (CDT)
Received: from orsfmr100.jf.intel.com (orsfmr100.jf.intel.com [10.7.209.16])
by orsfmr003.jf.intel.com (8.12.10/8.12.10/d: major-outer.mc,v 1.1 2004/09/17 17:50:56 root Exp $) with ESMTP id j44NooSl029043
for ; Wed, 4 May 2005 23:50:50 GMT
Received: from orsmsxvs041.jf.intel.com (orsmsxvs041.jf.intel.com [192.168.65.54])
by orsfmr100.jf.intel.com (8.12.10/8.12.10/d: major-inner.mc,v 1.2 2004/09/17 18:05:01 root Exp $) with SMTP id j44NoRIQ006155
for ; Wed, 4 May 2005 23:50:50 GMT
Received: from orsmsx332.amr.corp.intel.com ([192.168.65.60])
by orsmsxvs041.jf.intel.com (SAVSMTP 3.1.7.47) with SMTP id M2005050416504903912
for ; Wed, 04 May 2005 16:50:49 -0700
Received: from orsmsx401.amr.corp.intel.com ([192.168.65.207]) by orsmsx332.amr.corp.intel.com with Microsoft SMTPSVC(6.0.3790.211);
Wed, 4 May 2005 16:50:49 -0700
X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
charset="us-ascii"
Subject: RE: IEEE 754 standard is being revised
Date: Wed, 4 May 2005 16:50:48 -0700
Message-ID:
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: IEEE 754 standard is being revised
Thread-Index: AcVQ9+sxFTkcyh9JQfyWKU1iFEkRngACzEdg
From: "Kidder, Jeff"
To:
X-OriginalArrivalTime: 04 May 2005 23:50:49.0724 (UTC) FILETIME=[195E0BC0:01C55104]
X-Scanned-By: MIMEDefang 2.44
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by interval.louisiana.edu id j44NpjkG004541
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
I am the Vice chair of the 754r committee and have been lurking here for
a little while. I am very interested in gathering input for the
committee from the interval arithmetic folks. Your interests are often
invoked in discussions, but it is unclear if we really have a clear view
of your needs.
The article is particularly looking for input on uses of signaling NaNs.
We are also trying to define min and max operations, but we do not have
universal agreement on the right treatment of -0 and NaN in these
operations.
In particular, there is an impression among many that -0 is used in
interval arithmetic applications as distinct from +0. Is this actually
the case? I have seen treatments of intervals which don't seem to need
this distinction.
You can see a summary of the revision effort at
http://en.wikipedia.org/wiki/IEEE_754r
with links to other sites.
Cheers,
Jeff Kidder
-----Original Message-----
From: owner-reliable_computing [at] interval [dot] louisiana.edu
[mailto:owner-reliable_computing [at] interval [dot] louisiana.edu] On Behalf Of
Vladik Kreinovich
Sent: Wednesday, May 04, 2005 1:40 PM
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: IEEE 754 standard is being revised
The latest May 2005 issue of IEEE Computer has a short article by
William Kahan
and Dan Zuras from the IEEE 754 revision committee. Some of the issues
they
raise, e.g., the effect of round-off errors on the computational
results, are
very relevant to us.
IEEE is a very important source of standards for computer design and
use, so
their decisions are of extreme importance to us.
Maybe someone can clarify the situation to the mailing list - if our
viewpoint
is already being promoted great. If not sufficiently, maybe there is
something
we as a community can do.
Vladik
From owner-reliable_computing [at] interval [dot] louisiana.edu Sun May 8 14:56:30 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j48JuTcP012426
for ; Sun, 8 May 2005 14:56:30 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j48JuTxa012425
for reliable_computing-outgoing; Sun, 8 May 2005 14:56:29 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j48JuL6N012421
for ; Sun, 8 May 2005 14:56:27 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j48Jt4I23363
for ; Sun, 8 May 2005 13:55:04 -0600 (MDT)
Message-Id: <200505081955.j48Jt4I23363 [at] cs [dot] utep.edu>
Date: Sun, 8 May 2005 13:55:04 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: FYI
To: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: sfl+Qv9emu6wgckOh/i+iw==
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
"Evaluating a Patent System Gone Awry"
Traction for major patent system reforms is starting to build on Capitol
Hill as overwhelmed patent examiners approve applications for dubious
patents and infringement lawsuits snarl the courts. The system in its
current form has also encouraged a new kind of entrepreneur, or "troll," ...
http://www.acm.org/technews/articles/2005-7/0506f.html#item9
From owner-reliable_computing [at] interval [dot] louisiana.edu Sun May 8 21:17:13 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j492HDaL012858
for ; Sun, 8 May 2005 21:17:13 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j492HC1S012857
for reliable_computing-outgoing; Sun, 8 May 2005 21:17:12 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j492H4kU012853
for ; Sun, 8 May 2005 21:17:10 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j492G2j24799;
Sun, 8 May 2005 20:16:02 -0600 (MDT)
Message-Id: <200505090216.j492G2j24799 [at] cs [dot] utep.edu>
Date: Sun, 8 May 2005 20:16:03 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: geoinformatics meetings: 2005 and 2006
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: vladik [at] cs [dot] utep.edu, keller [at] utep [dot] edu, baru [at] sdsc [dot] edu, mbanton [at] sdsc [dot] edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: pVAcfmXn69Y0w7+Y7r6CpQ==
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
Dear Friends,
I have just returned from the National Meeting on Research Frontiers
in Cyberinfrastructure for the Geosciences GEON'2005 that was held in
San Diego, California, on May 5-6, 2005. At this meeting, sponsored by
the National Science Foundation and by the San Diego Supercomputer
Center, many interesting talks were presented by researchers in
geosciences and in computational sciences.
In addition to the talks presenting new results and methods,
the meeting included discussion of challenges and open
problems. During this discussion, several participants emphasized
the importance of handling uncertainty.
Detailed info about this conference can be obtained from the website
http://www.geongrid.org/AM05/
The organizers plan to have a large-scale International
Conference on Cyberinfrastructure in Geosciences in 2006. A preliminary
plan is to have it in early May 2006 in Washington, DC.
Professor G. Randy Keller, science editor of the Geosphere,
a new journal published by the Geological Society of America,
plans to devote a special issue of the journal to
selected papers presented at the GEON'2006 conference.
Mark your calendars!
Vladik
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu May 12 07:38:10 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CCcA9v021026
for ; Thu, 12 May 2005 07:38:10 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4CCcAOt021025
for reliable_computing-outgoing; Thu, 12 May 2005 07:38:10 -0500 (CDT)
Received: from lakermmtao12.cox.net (lakermmtao12.cox.net [68.230.240.27])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CCc0m4021020
for ; Thu, 12 May 2005 07:38:06 -0500 (CDT)
Received: from Inspiron-8200 ([68.226.133.93]) by lakermmtao12.cox.net
(InterMail vM.6.01.04.00 201-2131-118-20041027) with SMTP
id <20050512123652.PYUM10612.lakermmtao12.cox.net@Inspiron-8200>
for ;
Thu, 12 May 2005 08:36:52 -0400
Message-Id: <2.2.32.20050512123645.00bcaf28 [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, 12 May 2005 07:36:45 -0500
To: reliable_computing [at] interval [dot] louisiana.edu
From: "R. Baker Kearfott"
Subject: Validation of Positive Definiteness?
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Colleagues,
What is the best algorithm of which you are aware for rigorously
verifying that a point matrix is positive definite?
(Feel free to answer to the list, as you wish.)
Best regards,
Baker
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu May 12 08:53:23 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CDrN0D021121
for ; Thu, 12 May 2005 08:53:23 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4CDrMLO021120
for reliable_computing-outgoing; Thu, 12 May 2005 08:53:22 -0500 (CDT)
Received: from sys35.mail.msu.edu (sys35.mail.msu.edu [35.9.75.135])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CDrD8w021115
for ; Thu, 12 May 2005 08:53:19 -0500 (CDT)
Received: from c-24-11-149-116.hsd1.mi.comcast.net ([24.11.149.116] helo=TP570MSUMB)
by sys35.mail.msu.edu with esmtpsa (Exim 4.44 #1)
(TLSv1:RC4-MD5:128)
id 1DWE6e-0001o7-J5; Thu, 12 May 2005 09:52:04 -0400
From: "Martin Berz"
To: "R. Baker Kearfott" ,
Subject: RE: Validation of Positive Definiteness?
Date: Thu, 12 May 2005 09:52:00 -0400
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1478
In-Reply-To: <2.2.32.20050512123645.00bcaf28 [at] pop [dot] louisiana.edu>
X-Virus: None found by Clam AV
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Baker et al.,
the way we have been doing this is by LDL decomposition, which is a common
generalization of the Choleski decomposition for the case the matrix is not
necessarily positive definite, and executing the corresponding leading
algorithms in interval arithmetic. This allows to determine with certainty
whether the matrix is positive definite, whether it is not positive definite,
and may leave some undetermined cases.
Extensions are often of interest to find large positive definite subspaces if
the matrix is actually not positive definite, or if it is at the borderline
and can not be proven to be so with interval methods. The latter cases are
particularly useful for the applications in validated global optimization,
where the method when applied to the second order portions of Taylor models
allows to find lower bounds that avoid the cluster effect. Discussions of the
method (the QFB algorithm) can be found for example in the slides of a recent
talk at Savannah
http://www.gtrep.gatech.edu/rec/recworkshop/presentations/Berz.pdf
as well as in the following paper
M. Berz, K. Makino and Y. K. Kim,
Long-Term Stability of the Tevatron by Validated Global Optimization
Nuclear Instruments and Methods, in print
(I will post it on the MSU preprint server when I am in town)
Martin Berz
> -----Original Message-----
> From: owner-reliable_computing [at] interval [dot] louisiana.edu
> [mailto:owner-reliable_computing [at] interval [dot] louisiana.edu]On Behalf Of R.
> Baker Kearfott
> Sent: Thursday, May 12, 2005 8:37 AM
> To: reliable_computing [at] interval [dot] louisiana.edu
> Subject: Validation of Positive Definiteness?
>
>
> Colleagues,
>
> What is the best algorithm of which you are aware for rigorously
> verifying that a point matrix is positive definite?
>
> (Feel free to answer to the list, as you wish.)
>
> Best regards,
>
> Baker
>
> ---------------------------------------------------------------
> R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
> (337) 482-5270 (work) (337) 993-1827 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> (Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
>
>
>
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu May 12 08:55:37 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CDtbCm021128
for ; Thu, 12 May 2005 08:55:37 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4CDtaA8021127
for reliable_computing-outgoing; Thu, 12 May 2005 08:55:36 -0500 (CDT)
Received: from sys35.mail.msu.edu (sys35.mail.msu.edu [35.9.75.135])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CDtSuw021123
for ; Thu, 12 May 2005 08:55:33 -0500 (CDT)
Received: from c-24-11-149-116.hsd1.mi.comcast.net ([24.11.149.116] helo=TP570MSUMB)
by sys35.mail.msu.edu with esmtpsa (Exim 4.44 #1)
(TLSv1:RC4-MD5:128)
id 1DWE8q-0002AD-Oe; Thu, 12 May 2005 09:54:21 -0400
From: "Martin Berz"
To: "R. Baker Kearfott" ,
Subject: RE: Validation of Positive Definiteness?
Date: Thu, 12 May 2005 09:54:16 -0400
Message-ID:
MIME-Version: 1.0
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1478
In-Reply-To: <2.2.32.20050512123645.00bcaf28 [at] pop [dot] louisiana.edu>
X-Virus: None found by Clam AV
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Baker et al.,
the way we have been doing this is by LDL decomposition, which is a common
generalization of the Choleski decomposition for the case the matrix is not
necessarily positive definite, and executing the corresponding leading
algorithms in interval arithmetic. This allows to determine with certainty
whether the matrix is positive definite, whether it is not positive definite,
and may leave some undetermined cases.
Extensions are often of interest to find large positive definite subspaces if
the matrix is actually not positive definite, or if it is at the borderline
and can not be proven to be so with interval methods. The latter cases are
particularly useful for the applications in validated global optimization,
where the method when applied to the second order portions of Taylor models
allows to find lower bounds that avoid the cluster effect. Discussions of the
method (the QFB algorithm) can be found for example in the slides of a recent
talk at Savannah
http://www.gtrep.gatech.edu/rec/recworkshop/presentations/Berz.pdf
as well as in the following paper
M. Berz, K. Makino and Y. K. Kim,
Long-Term Stability of the Tevatron by Validated Global Optimization
Nuclear Instruments and Methods, in print
(I will post it on the MSU preprint server when I am in town)
Martin Berz
> -----Original Message-----
> From: owner-reliable_computing [at] interval [dot] louisiana.edu
> [mailto:owner-reliable_computing [at] interval [dot] louisiana.edu]On Behalf Of R.
> Baker Kearfott
> Sent: Thursday, May 12, 2005 8:37 AM
> To: reliable_computing [at] interval [dot] louisiana.edu
> Subject: Validation of Positive Definiteness?
>
>
> Colleagues,
>
> What is the best algorithm of which you are aware for rigorously
> verifying that a point matrix is positive definite?
>
> (Feel free to answer to the list, as you wish.)
>
> Best regards,
>
> Baker
>
> ---------------------------------------------------------------
> R. Baker Kearfott, rbk [at] louisiana [dot] edu (337) 482-5346 (fax)
> (337) 482-5270 (work) (337) 993-1827 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> (Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
>
>
>
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu May 12 09:13:27 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CEDRdh021154
for ; Thu, 12 May 2005 09:13:27 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4CEDQCT021153
for reliable_computing-outgoing; Thu, 12 May 2005 09:13:26 -0500 (CDT)
Received: from wminf0.math.uni-wuppertal.de (wminf0.math.uni-wuppertal.de [132.195.94.17])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CEDHKO021149
for ; Thu, 12 May 2005 09:13:23 -0500 (CDT)
Received: from math.uni-wuppertal.de (wmai02.math.uni-wuppertal.de [132.195.95.2])
by wminf0.math.uni-wuppertal.de (8.9.3+Sun/8.9.3) with ESMTP id QAA06981
for ; Thu, 12 May 2005 16:12:09 +0200 (MEST)
Message-ID: <42836439.5050503 [at] math [dot] uni-wuppertal.de>
Date: Thu, 12 May 2005 16:12:09 +0200
From: Andreas Frommer
Organization: Faculty of Science, Department of Mathematics
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4.3) Gecko/20050104
X-Accept-Language: en-us, en, de
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Validation of Positive Definiteness
X-Enigmail-Version: 0.76.8.0
X-Enigmail-Supports: pgp-inline, pgp-mime
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
>
>
>Baker Kearfott asked
>
>Colleagues,
>
>What is the best algorithm of which you are aware for rigorously
>verifying that a point matrix is positive definite?
>
>(Feel free to answer to the list, as you wish.)
>
>Best regards,
>
>Baker
>
>
In my view, the way Siegfried Michael Rump obtains guaranteed l2-error
bounds for solutions of symmetric positive definite
and sparse linear systems (implemented in Intlab?) is a good way to work
on this problem, provided the answer is "yes"
(the matrix is symmetric positive definite)
It works as follws:
Given matrix A, symmetric, expected to be positive definite
Step 1: Perform inverse iteration to find approximation a to the
smallest eigenvalue
Step 2: if a is not positive --> stop (A is probably not spd)
if a is positive, chose some b with 0 < b < a, for example
b = 0.9*a
Step 3: Compute a floating point Cholesky factorization A-bI = L L^T
Step 4: Using directed rounding, compute an upper bound for the matrix B
=| A-bI - L L^T|.
Step 5: If the row sum norm of B (or any other l_p-norm) is less than b,
then A is positive definite by the Bauer-Fike theorem,
and the minimal eigenvalue of A is not less than b minus
that norm,.
Andreas
From owner-reliable_computing [at] interval [dot] louisiana.edu Thu May 12 11:10:21 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CGALBG021424
for ; Thu, 12 May 2005 11:10:21 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4CGAKkm021423
for reliable_computing-outgoing; Thu, 12 May 2005 11:10:20 -0500 (CDT)
Received: from smtp2.rz.tu-harburg.de (smtp2.rz.tu-harburg.de [134.28.205.13])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4CGABnZ021416
for ; Thu, 12 May 2005 11:10:17 -0500 (CDT)
Received: from mail2.rz.tu-harburg.de (mail2.rz.tu-harburg.de [134.28.202.179])
by smtp2.rz.tu-harburg.de (8.13.1/8.13.1) with ESMTP id j4CG97uh004127
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK);
Thu, 12 May 2005 18:09:07 +0200
Received: from oem-9n90y5vdt8b (d055163.adsl.hansenet.de [80.171.55.163])
(user=ti3sr mech=LOGIN bits=0)
by mail2.rz.tu-harburg.de (8.13.1/8.13.1) with ESMTP id j4CG94sH020347
(version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NO);
Thu, 12 May 2005 18:09:05 +0200
To: "Andreas Frommer" ,
reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: Validation of Positive Definiteness
References: <42836439.5050503 [at] math [dot] uni-wuppertal.de>
Message-ID:
Date: Thu, 12 May 2005 18:09:01 -0000
From: "Siegfried M. Rump"
Organization: Technical University Hamburg-Harburg
Content-Type: text/plain; format=flowed; delsp=yes; charset=iso-8859-15
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
In-Reply-To: <42836439.5050503 [at] math [dot] uni-wuppertal.de>
User-Agent: Opera M2/8.0 (Win32, build 7561)
X-Scanned-By: TUHH Rechenzentrum content checker on 134.28.205.13
X-Scanned-By: TUHH Rechenzentrum content checker on 134.28.202.179
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Hello everybody,
yes, this is the way it is implemented in INTLAB in the
function 'verifylss' (for sparse matrices).
The latest version 5.1 of INTLAB contains a function 'isspd'
based on floating-point Cholesky and rigorous estimation
of rounding errors. It is very fast because only one
(pure fl-pt) Cholesky decomposition is needed.
The method is described in the paper together with T. Ogita
on 'super-fast algorithms for linear systems' describing
a method where the complete verification process for s.p.d.
systems requires the same computing time as one fl-pt
Cholesky decomposition. The paper was presented at the
last SCAN conference in Fukuoka.
Best wishes
Siegfried M. Rump
On Thu, 12 May 2005 14:12:09 -0000, Andreas Frommer
wrote:
>>
>>
>> Baker Kearfott asked
>>
>
>
>> Colleagues,
>>
>> What is the best algorithm of which you are aware for rigorously
>> verifying that a point matrix is positive definite?
>>
>> (Feel free to answer to the list, as you wish.)
>>
>> Best regards,
>>
>> Baker
>>
>
>
> In my view, the way Siegfried Michael Rump obtains guaranteed l2-error
> bounds for solutions of symmetric positive definite
> and sparse linear systems (implemented in Intlab?) is a good way to work
> on this problem, provided the answer is "yes"
> (the matrix is symmetric positive definite)
>
> It works as follws:
>
> Given matrix A, symmetric, expected to be positive definite
>
> Step 1: Perform inverse iteration to find approximation a to the
> smallest eigenvalue
> Step 2: if a is not positive --> stop (A is probably not spd)
> if a is positive, chose some b with 0 < b < a, for example
> b = 0.9*a
> Step 3: Compute a floating point Cholesky factorization A-bI = L L^T
> Step 4: Using directed rounding, compute an upper bound for the matrix B
> =| A-bI - L L^T|.
> Step 5: If the row sum norm of B (or any other l_p-norm) is less than b,
> then A is positive definite by the Bauer-Fike theorem,
> and the minimal eigenvalue of A is not less than b minus
> that norm,.
>
>
>
> Andreas
>
--
=================================================
Prof. Dr. Siegfried M. Rump
Arbeitsbereich Informatik III
Technische Universität Hamburg-Harburg
Schwarzenbergstr. 95
21071 Hamburg
Germany
phone +49 40 42878 3027
secr. +49 40 42878 3227
fax +49 40 42878 2489
From owner-reliable_computing [at] interval [dot] louisiana.edu Sat May 14 09:04:03 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4EE43gO025541
for ; Sat, 14 May 2005 09:04:03 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4EE43j9025540
for reliable_computing-outgoing; Sat, 14 May 2005 09:04:03 -0500 (CDT)
Received: from webmail-5.wideopenwest.com (webmail-5.wowway.com [64.233.207.42])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4EE3sE7025536
for ; Sat, 14 May 2005 09:03:59 -0500 (CDT)
Received: from wideopenwest.com (localhost.localdomain [127.0.0.1])
by webmail-5.wideopenwest.com (8.12.8/8.12.8) with ESMTP id j4EE2tnv023983
for ; Sat, 14 May 2005 09:02:59 -0500
From: "Rich Miller"
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: integration of interval ODEs
Date: Sat, 14 May 2005 09:02:55 -0600
Message-Id: <20050514134424.M59568 [at] wideopenwest [dot] com>
X-Mailer: Open WebMail 2.30 20040131
X-OriginatingIP: 64.53.233.236 (rmiller7)
MIME-Version: 1.0
Content-Type: text/plain;
charset=iso-8859-1
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
please reply directly, I will summarize for the list
I am looking at problems involving integration of an
ordinary differential equation with interval parameters
and need a quick survey of solvers that can handle this.
the computation may be repeated several times with
changes to the parameters but not the basic form of the
ODE. I would like to be able to deal with this iteration
under programmatic control, so a standardized package
may not be flexible enough.
Rich Miller
rmiller7 [at] wideopenwest [dot] com
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri May 20 07:25:41 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4KCPec4003022
for ; Fri, 20 May 2005 07:25:40 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4KCPedv003021
for reliable_computing-outgoing; Fri, 20 May 2005 07:25:40 -0500 (CDT)
Received: from interferon.mpi-sb.mpg.de (mail.mpi-sb.mpg.de [139.19.1.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4KCPV9k003017
for ; Fri, 20 May 2005 07:25:37 -0500 (CDT)
Received: from amavis by interferon.mpi-sb.mpg.de with scanned-ok (Exim 3.36 #1 (Debian))
id 1DZ6XS-0005Q2-00
for ; Fri, 20 May 2005 14:23:38 +0200
Received: from mpino2303.ag2.mpi-sb.mpg.de ([139.19.24.75])
by interferon.mpi-sb.mpg.de with esmtp (Exim 3.36 #1 (Debian))
id 1DZ6XQ-0005Mj-00; Fri, 20 May 2005 14:23:36 +0200
Subject: IntCP 2005 workshop
From: Stefan Ratschan
To: reliable_computing [at] interval [dot] louisiana.edu
Content-Type: text/plain
Date: Fri, 20 May 2005 14:23:06 +0200
Message-Id: <1116591786.3416.53.camel@localhost>
Mime-Version: 1.0
X-Mailer: Evolution 2.0.3
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: by AMaViS perl-11
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
(we apologize for possible multiple reception of this call)
=================================================================
CALL FOR PAPERS
IntCP 2005 workshop
Interval Analysis and Constraint Propagation for Applications
Melia Sitges Hotel
Sitges (Barcelona) Spain
1st October 2005
Held in conjunction with the
Eleventh International Conference on Principles
and Practice of Constraint Programming (CP 2005)
=================================================================
* Important Dates:
------------------
04 Jul 2005 - Submission deadline
29 Jul 2005 - Notification of acceptance
01 Aug 2005 - Early registration deadline
16 Aug 2005 - Final camera-ready copies
01 Oct 2005 - Workshop day
* Description and goals:
------------------------
Since most physical laws are formulated as numerical constraints,
problem areas that use physical models usually involve such
constraints (e.g., robotics, control). Moreover, todays computing
systems are more and more embedded into their physical environment
(modern cars contain thousands of microprocessors), resulting in
models of the total system that contain numerical constraints in an
essential way. Constraint propagation solvers are appealing for
solving numerical problems because they can guarantee two essential
properties:
* _completeness_ which means the ability to find all solutions if
any, or else to prove that there are no solutions to the problem,
* _rigor_ which means that the rounding errors due to
floating-point computation can be rigorously controlled.
These two properties are essential in many practical applications. For
instance, real-world problems often have a continuum of solutions
which express a spectrum of equally relevant choices, as the possible
moving areas of a mobile robot, the collision regions between objects
in mechanical assembly, or different alternatives of shapes for the
components of a kinematic chain. These alternatives must be
identified as completely and rigorously as possible.
Moreover, constraint propagation techniques can flexibly incorporate
relaxation techniques and the handling of preferences. This is also an
important feature since many applications lead to over-constrained
problems.
However, while constraint propagation solvers have proven particularly
efficient in solving challenging instances of numerical problems with
nonlinear constraints, they do not yet have enough appeal in many
practical problem areas. One of the reasons is that they generally
provide representation of the solution set that are either
prohibitively verbose or poorly informative. Recent advances have
shown however that this matter of fact was not an intrinsinc
limitation and that constraint propagation can be considerably
improved by incorporating techniques from interval analysis and global
optimization.
One of the goals of this workshop is to explore the complementarity of
different approaches and how it can be used to produce _practical_
powerful solvers. Other topics often relevant in applications are:
* integrating uncertainty that can, for example, be modeled, by
logical quantifiers,
* exploiting specific problem structure, for example in the case of
discrete time, continuous state systems,
* handling mixture of discrete and continuous problem variables,
* developing specific techniques for inequality constraints or
problems with a huge number of discrete solutions,
* improving solution selection by means of preferences or solution
space "browsing"
We seek contributions that address such questions, and present
relevant software tools, algorithms, theoretical results, or
applications of constraint propagation and interval analysis
techniques oriented toward real-world problems.
* Workshop format:
------------------
This is a half-day workshop, open to the entire community . Its aim is
to provide a forum where researchers currently working in this area
can discuss their most recent ideas and developments and think
together about the most promising new directions. We particularly
encourage the presentation of work that bridge the gap between theory
and practice.
* Submissions:
--------------
People wishing to give a talk should submit an extended abstract of at
least 2 pages. Submissions must be formatted using LNCS packages (see
CP formatting instructions). The title page should include the name,
address, telephone number and electronic mailing address for each
author. Please, email all submissions in postscript or pdf format to :
intcp-sub@mpi-sb.mpg.de
by July 04th 2005, specifying the name of the contact author in the
message.
At least one author of each accepted submission must attend the
workshop to present the paper.
The accepted papers will appear in the workshop proceedings, which
will be distributed to the participants.
* Reviewing process:
--------------------
Submissions will be reviewed by at least one committee member, and
will be selected on the basis of their contribution to the topic of
the workshop. Authors will receive feedback in the form of reviewers'
comments.
* Accomodation/Registration:
----------------------------
Accomodation is provided by the hosting conference CP 2005. All
workshop attendees must pay the workshop fee. It is however possible
to attend the workshop without paying the CP 2005 regular registration
fee.
Please note that a single CP 2005 registration fee provides entry to
all CP and ICLP workhops.
* Committee:
------------
- Frederic Goualard, University of Nantes, France.
- Tim Hickey, Brandeis University, USA.
- Luc Jaulin, ENSIETA Brest, France.
- Christophe Jermann, University of Nantes, France (co-organizer).
- Jean-Pierre Merlet, National Institute for Informatics and Control,
France.
- Stefan Ratschan, Max-Planck Institut fuer Informatik, Germany
(co-organizer).
- Djamila Sam-Haroud, EPFL, Switzerland (co-organizer).
- Josep Vehi, University of Girona, Spain.
* Contacts:
-----------
Send questions about the workshop to : intcp-oc@mpi-sb.mpg.de
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri May 27 09:23:56 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RENupP017375
for ; Fri, 27 May 2005 09:23:56 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4RENutQ017374
for reliable_computing-outgoing; Fri, 27 May 2005 09:23:56 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RENl80017370
for ; Fri, 27 May 2005 09:23:53 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j4RELrq08459;
Fri, 27 May 2005 08:21:53 -0600 (MDT)
Message-Id: <200505271421.j4RELrq08459 [at] cs [dot] utep.edu>
Date: Fri, 27 May 2005 08:21:52 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: ISSAC2005CFParticip
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: issac2005 [at] mmrc [dot] iss.ac.cn
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: 0FEgPaE3p8w6A0gU+SG5Iw==
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
forwarding. Vladik
------------- Begin Forwarded Message -------------
Date: Fri, 27 May 2005 17:02:37 +0800
From: ISSAC 2005
To: vladik [at] cs [dot] utep.edu
Subject: ISSAC2005CFParticip
X-Scanned-By: MIMEDefang 2.44
ISSAC2005 Call for Participation
International Symposium on Symbolic and Algebraic Computation
July 24-27, 2005, Beijing, China.
http://www.mmrc.iss.ac.cn/issac2005/
The On-Line Registration for ISSAC2005 is open. The deadline of
early registration is June 20, 2005. You are welcome to
participate ISSAC2005.
The ISSAC2005 program consists of
Forty Eight Contributed Talks
Poster Presentations
Software Exhibitions
Invited Talks
Bruno Buchberger, RISC-Linz, Austria
Bruno Salvy, INRIA, France
Wen-Tsun Wu, Chinese Academy of Sciences, China
Tutorials
Evelyne Hubert INRIA, Sophia Antipolis, France
Arnaud Tisserand INRIA, Lyon, France
Jan Verschelde University of Chicago, USA
Satellite Workshops
Algebraic Methods in Cryptography
Internet Accessible Mathematical Computation
Symbolic-Numeric Computation
------------- End Forwarded Message -------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri May 27 11:34:06 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RGY5Mh017592
for ; Fri, 27 May 2005 11:34:05 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4RGY575017591
for reliable_computing-outgoing; Fri, 27 May 2005 11:34:05 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RGXuCW017587
for ; Fri, 27 May 2005 11:34:02 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j4RGW4A09294;
Fri, 27 May 2005 10:32:04 -0600 (MDT)
Message-Id: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu>
Date: Fri, 27 May 2005 10:32:02 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: from SIAM Review
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: SCArTqONVL0wYXgyf1uCtg==
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
Dear Friends,
This is just FYI.
The lastest June 2005 issue of SIAM Review (Vol. 47, No. 2) has a review of the
SIAM 100-Digit Challenge book (SIAM, 2004) by Nicholas J. Higham, who says:
"Wagon's chapter "Think Globally, Act Locally shows how interval analysis can
be used to solve a gloabl minimization problem in two variables; in doing so it
provides the best summary of the benefits of interval analysis that I have
seen"
Vladik
P.S. I check with Google, a version of this chapter is posted on
www-m8.mathematik.tu-muenchen.de/ m3/ftp/Bornemann/pdf/chap4.pdf
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri May 27 13:14:32 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RIEWqQ017769
for ; Fri, 27 May 2005 13:14:32 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4RIEVJ6017768
for reliable_computing-outgoing; Fri, 27 May 2005 13:14:31 -0500 (CDT)
Received: from imap1u.univie.ac.at (imap1u.univie.ac.at [131.130.1.182])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RIEMtQ017764
for ; Fri, 27 May 2005 13:14:28 -0500 (CDT)
Received: from [131.130.16.23] (theseus.mat.univie.ac.at [131.130.16.23])
(authenticated bits=0)
by imap1u.univie.ac.at (8.12.10/8.12.10) with ESMTP id j4RIC5KE068731
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Fri, 27 May 2005 20:12:06 +0200 (CEST)
Message-ID: <429762F5.5090706 [at] univie [dot] ac.at>
Date: Fri, 27 May 2005 20:12:05 +0200
From: Arnold Neumaier
Organization: University of Vienna
User-Agent: Mozilla Thunderbird 1.0.2-1.3.2 (X11/20050324)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: Vladik Kreinovich
CC: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Subject: Re: from SIAM Review
References: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu>
In-Reply-To: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-DCC-ZID-Univie-Metrics: mx8 4248; Body=4 Fuz1=4 Fuz2=4
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Vladik Kreinovich wrote:
> The lastest June 2005 issue of SIAM Review (Vol. 47, No. 2) has a review of the
> SIAM 100-Digit Challenge book (SIAM, 2004) by Nicholas J. Higham, who says:
>
> "Wagon's chapter "Think Globally, Act Locally shows how interval analysis can
> be used to solve a gloabl minimization problem in two variables; in doing so it
> provides the best summary of the benefits of interval analysis that I have
> seen"
>
> P.S. I check with Google, a version of this chapter is posted on
> www-m8.mathematik.tu-muenchen.de/ m3/ftp/Bornemann/pdf/chap4.pdf
[note: no blank before m3!]
The author presents on p.85 a branch and bound scheme with
quadrisection and monotonicity test for bound-onstrained
global minimization, and on p. 95 Krawczyk's method for
solving a system of equations [to be applied to the gradient].
The summary Higham alludes to appears to be that on p.95/96:
''the fact that the very simplest ideas give a veri ed answer to Problem
4 in a few seconds and with only a few lines of code shows how powerful
these ideas are. And it is noteworthy that interval analysis has played
an important role in diverse areas of modern mathematics. For example,W.
Tucker won the Moore prize for his recent work using interval analysis
to prove that the Lorenz equations really do have a strange attractor;
this solved one of Steven Smale s Problems for the 21st Century (see
[Tuc02]); Hales and Ferguson [FH98] used interval methods in their
resolution of the Kepler conjecture on sphere-packing, and Lanford
[Lan82] used intervals to prove the existence of a universal limit the
Feigenbaum constant in certain sequences of bifurcations.''
''The most important points of the interval approach to Problem 4 are:
* The algorithm is very general and will find the lowest critical point
in the rectangle (provided interval arithmetic is available in a form
that applies to the objective function and its partial derivatives).
* The results are verifiably correct if one uses intervals throughout.
* Getting the results to very high precision is not a problem.
* Having an interval root- nding method can lead to improvements in the
optimization algorithm.
* And most important: The interval algorithm is a reasonable way to
solve the problem whether or not one wants proved results. In short,
interval thinking yields both a good algorithm and proved results.
* The basic ideas apply to functions of more variables, but life becomes
more diffcult in higher dimensions. See [Han92, Kea96] for discussions
of various enhancements that can be used to improve the basic algorithm
(one example: using the Hessian to eliminate n-dimensional intervals on
which the function is not concave up).''
As for algorithmic improvements, one should rather consult more recent
work, such as the surveys
A. Neumaier,
Complete Search in Continuous Global Optimization and Constraint
Satisfaction,
pp. 271-369 in: Acta Numerica 2004 (A. Iserles, ed.),
Cambridge University Press 2004.
A. Neumaier, O. Shcherbina, W. Huyer and T. Vinko,
A comparison of complete global optimization solvers,
Mathematical Programming, Online first publication, May 6, 2005,
Arnold Neumaier
From owner-reliable_computing [at] interval [dot] louisiana.edu Fri May 27 14:39:12 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RJdCZC017839
for ; Fri, 27 May 2005 14:39:12 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4RJdCoN017838
for reliable_computing-outgoing; Fri, 27 May 2005 14:39:12 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4RJd4TB017834
for ; Fri, 27 May 2005 14:39:09 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j4RJb4t10505;
Fri, 27 May 2005 13:37:04 -0600 (MDT)
Message-Id: <200505271937.j4RJb4t10505 [at] cs [dot] utep.edu>
Date: Fri, 27 May 2005 13:37:04 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: CFP DSCP'05
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: qFieImZAhLL5o3b1GP81BA==
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
forwarding. Vladik
*****************************************
From: Martine Ceberio
This is about constraints in multi-agent environments,
but I think this workshop can be interesting for the
interval community as well, as we know intervals are
useful when dealing with continuous constraints.
-----------------------------------------------
Apologies if you receive multiple copies
-----------------------------------------------
CALL FOR PAPER:
1st International Workshop on:
Distributed and Speculative Constraint Processing
--- DSCP'05 ---
http://www.cs.utep.edu/mceberio/Research/Conferences/DSCP05/
held in conjunction with:
the 11th International Conference on
Principles and Practice of Constraint Programming, CP'2005
October 1 - 5, 2005
Melia Sitges Hotel
Sitges (Barcelona) - Spain
------------------------------------------------
Overview:
DSCP'05 addresses constraint processing techniques in distributed
environments, with a special interest on speculative computations.
A distributed constraint satisfaction problem (usually referred to
as DisCSP) is a constraint satisfaction problem (CSP) in which multiple
agents are involved. DisCSPs arise when pieces of the whole problem
can be discharged / allocated to agents. These agents are generally
independent (autonomous), but able to communicate, basically to let
the others know (depending on the communication protocol) the result
of their inner solving process. Pieces of the global problem may be,
depending on the problem, variables, or constraints, or both.
Many problems in Multi-Agent Systems (MAS) can be formalized as
DisCSPs. Therefore, we expect this workshop to impact a wide range
of people, more specifically a lot of people involved in both CSP and
MAS, or in either of these. Multi-agent systems are indeed very
fashionable and convenient, for they make it possible, for instance, to
take advantage of multi-processor machines, and for they also make it
possible to design human-like efficient organizations of agents.
In addition to work on plain DisCSP, our workshop aims at emphasizing
the process of speculative computations among agents. Indeed, even if
multi-agent systems are very fashionable and convenient, their main
limitation is that, as arises in human organizations, communication may
be an issue: delayed or broken, it leads to incompleteness of the
information in the reasoning structure. This is a concrete concern when
we consider distributed systems such as the Internet, in which
communication is indeed not guaranteed, and even if we could guarantee
it, communication may either take time, or agents themselves may delay
their sending information. In the case of such not ideal but practical
situations, when problem-solving is at stake, frameworks for speculative
computations can constitute a solution. Some work was already carried out
on speculative constraint processing, but only in master-slave systems.
-----------------------------------------------
Scope of DSCP:
In this workshop, we would be pleased to gather together researchers
interested in all aspects of distributed and/or speculative constraint
solving, such as:
* frameworks for DisCSPs
* algorithms
* communication protocols in DisCSPs
* theoretical issues, such as space complexity
* handling over-constrained DisCSPs, as well as performing optimization
using DisCSPs
* applications of DisCSPs
* frameworks for speculative computations in MAS
* theoretical work on communication protocols for speculative computation
in MAS
* algorithms for DisCSP solving with speculative computation
* applications
* ...
We encourage in particular the submission of work in progress, of work
on very specialized aspects of distributed and/or speculative constraint
processing, and of work emphasizing real applications of DSCP.
------------------------------------------------
Submission:
Prospective attendees can submit a paper, which can be up to 15 pages
in length. Authors will submit their papers electronically in postscript
or pdf format. Papers should be formatted using the Lecture Notes in
Computer Science (LNCS) style.
Please send your submissions by email to mceberio [at] cs [dot] utep.edu, with
DSCP'05 Workshop Submission, as the subject of the email.
-------------------------------------------------
Important note:
The workshop is open to the entire community. All participants will have
to pay the registration fee that entitles them to participate in all CP/ICLP
workshops, and at least one author of each accepted paper must attend
the workshop.
------------------------------------------------
Important dates:
* Paper Submission deadline June 20th
* Notification of acceptance July 20th
* Deadline for early registration August, 1st
* Camera-ready version deadline August, 10th
* Workshop Date October, 1st
-----------------------------------------------
Organizing committee:
* Martine Ceberio (Primary contact)
University of Texas at El Paso - USA
e-mail: mceberio [at] cs [dot] utep.edu
url: http://www.cs.utep.edu/mceberio
* Makoto Yokoo
Kyushu University -- Fukuoka -- Japan
e-mail: yokoo [at] is [dot] kyushu-u.ac.jp
* Enrico Pontelli
New Mexico State University -- USA
e-mail: epontell [at] cs [dot] nmsu.edu
* Boi Faltings
EPFL -- Swiss Federal Institute of Technology -- Switzerland
e-mail: Boi.Faltings [at] epfl [dot] ch
* Weixiong Zhang
Washington University -- St. Louis -- USA
e-mail: zhang [at] cse [dot] wustl.edu
* Hiroshi Hosobe
National Institute of Informatics -- Tokyo -- Japan
e-mail: hosobe [at] nii [dot] ac.jp
* Jay Modi
Carnegie Mellon University -- Pittsburg -- USA
e-mail: pmodi [at] cs [dot] cmu.edu
------------------------------------------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Sun May 29 21:44:57 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4U2iuM8022584
for ; Sun, 29 May 2005 21:44:57 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4U2iutw022583
for reliable_computing-outgoing; Sun, 29 May 2005 21:44:56 -0500 (CDT)
Received: from ns.ict.nsc.ru (ns.ict.nsk.su [193.124.243.33])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4U2ifL1022579
for ; Sun, 29 May 2005 21:44:49 -0500 (CDT)
Received: from COMP0 (COMP0.ict.local.net [192.168.0.124])
by ns.ict.nsc.ru (8.13.3/8.13.3) with SMTP id j4U2h5eK087930;
Mon, 30 May 2005 09:43:05 +0700 (NOVST)
(envelope-from shary [at] ict [dot] nsc.ru)
X-Authentication-Warning: ns.ict.nsc.ru: Host COMP0.ict.local.net [192.168.0.124] claimed to be COMP0
Message-ID: <000d01c564c1$8028f240$7c00a8c0@COMP0>
From: "Sergey P. Shary"
To: "Arnold Neumaier" ,
"Vladik Kreinovich"
Cc: ,
References: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu> <429762F5.5090706 [at] univie [dot] ac.at>
Subject: Re: from SIAM Review
Date: Mon, 30 May 2005 09:44:25 +0700
Organization: ICT SB RAS
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.2800.1106
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Arnold,
Where did your homepage http://www.mat.univie.ac.at/~neum/ move?
The server http://www.mat.univie.ac.at responds that
" ... Die gesuchte URL wurde auf dem Server nicht gefunden"
Sergey P. Shary
----- Original Message -----
From: "Arnold Neumaier"
To: "Vladik Kreinovich"
Cc: ;
Sent: Saturday, May 28, 2005 1:12 AM
Subject: Re: from SIAM Review
> Vladik Kreinovich wrote:
>
> > The lastest June 2005 issue of SIAM Review (Vol. 47, No. 2) has a review of the
> > SIAM 100-Digit Challenge book (SIAM, 2004) by Nicholas J. Higham, who says:
> >
> > "Wagon's chapter "Think Globally, Act Locally shows how interval analysis can
> > be used to solve a gloabl minimization problem in two variables; in doing so it
> > provides the best summary of the benefits of interval analysis that I have
> > seen"
> >
>
> > P.S. I check with Google, a version of this chapter is posted on
> > www-m8.mathematik.tu-muenchen.de/ m3/ftp/Bornemann/pdf/chap4.pdf
>
> [note: no blank before m3!]
>
> The author presents on p.85 a branch and bound scheme with
> quadrisection and monotonicity test for bound-onstrained
> global minimization, and on p. 95 Krawczyk's method for
> solving a system of equations [to be applied to the gradient].
> The summary Higham alludes to appears to be that on p.95/96:
>
> ''the fact that the very simplest ideas give a veri ed answer to Problem
> 4 in a few seconds and with only a few lines of code shows how powerful
> these ideas are. And it is noteworthy that interval analysis has played
> an important role in diverse areas of modern mathematics. For example,W.
> Tucker won the Moore prize for his recent work using interval analysis
> to prove that the Lorenz equations really do have a strange attractor;
> this solved one of Steven Smale s Problems for the 21st Century (see
> [Tuc02]); Hales and Ferguson [FH98] used interval methods in their
> resolution of the Kepler conjecture on sphere-packing, and Lanford
> [Lan82] used intervals to prove the existence of a universal limit the
> Feigenbaum constant in certain sequences of bifurcations.''
>
> ''The most important points of the interval approach to Problem 4 are:
> * The algorithm is very general and will find the lowest critical point
> in the rectangle (provided interval arithmetic is available in a form
> that applies to the objective function and its partial derivatives).
> * The results are verifiably correct if one uses intervals throughout.
> * Getting the results to very high precision is not a problem.
> * Having an interval root- nding method can lead to improvements in the
> optimization algorithm.
> * And most important: The interval algorithm is a reasonable way to
> solve the problem whether or not one wants proved results. In short,
> interval thinking yields both a good algorithm and proved results.
> * The basic ideas apply to functions of more variables, but life becomes
> more diffcult in higher dimensions. See [Han92, Kea96] for discussions
> of various enhancements that can be used to improve the basic algorithm
> (one example: using the Hessian to eliminate n-dimensional intervals on
> which the function is not concave up).''
>
>
>
>
> As for algorithmic improvements, one should rather consult more recent
> work, such as the surveys
>
> A. Neumaier,
> Complete Search in Continuous Global Optimization and Constraint
> Satisfaction,
> pp. 271-369 in: Acta Numerica 2004 (A. Iserles, ed.),
> Cambridge University Press 2004.
>
> A. Neumaier, O. Shcherbina, W. Huyer and T. Vinko,
> A comparison of complete global optimization solvers,
> Mathematical Programming, Online first publication, May 6, 2005,
>
>
> Arnold Neumaier
>
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon May 30 06:02:24 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UB2NHS023526
for ; Mon, 30 May 2005 06:02:23 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4UB2NDh023525
for reliable_computing-outgoing; Mon, 30 May 2005 06:02:23 -0500 (CDT)
Received: from imap1u.univie.ac.at (imap1u.univie.ac.at [131.130.1.182])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UB2EVk023521
for ; Mon, 30 May 2005 06:02:20 -0500 (CDT)
Received: from [131.130.16.23] (theseus.mat.univie.ac.at [131.130.16.23])
(authenticated bits=0)
by imap1u.univie.ac.at (8.12.10/8.12.10) with ESMTP id j4UB0AKE068862
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
for ; Mon, 30 May 2005 13:00:13 +0200 (CEST)
Message-ID: <429AF239.3030203 [at] univie [dot] ac.at>
Date: Mon, 30 May 2005 13:00:09 +0200
From: Arnold Neumaier
Organization: University of Vienna
User-Agent: Mozilla Thunderbird 1.0.2-1.3.2 (X11/20050324)
X-Accept-Language: en-us, en
MIME-Version: 1.0
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: Re: from SIAM Review
References: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu> <429762F5.5090706 [at] univie [dot] ac.at> <000d01c564c1$8028f240$7c00a8c0@COMP0>
In-Reply-To: <000d01c564c1$8028f240$7c00a8c0@COMP0>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-DCC-ZID-Univie-Metrics: mx8 4249; Body=1 Fuz1=1 Fuz2=1
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Sergey P. Shary wrote:
>
> Where did your homepage http://www.mat.univie.ac.at/~neum/ move?
Our server had a heat stroke this weekend, and no one to take care of.
Now it should be fine again.
Arnold Neumaier
>>A. Neumaier,
>>Complete Search in Continuous Global Optimization and Constraint
>>Satisfaction,
>>pp. 271-369 in: Acta Numerica 2004 (A. Iserles, ed.),
>>Cambridge University Press 2004.
>>
>>A. Neumaier, O. Shcherbina, W. Huyer and T. Vinko,
>>A comparison of complete global optimization solvers,
>>Mathematical Programming, Online first publication, May 6, 2005,
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon May 30 10:21:07 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UFL6N7023896
for ; Mon, 30 May 2005 10:21:06 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4UFL6ni023895
for reliable_computing-outgoing; Mon, 30 May 2005 10:21:06 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UFKwZb023891
for ; Mon, 30 May 2005 10:21:03 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j4UFIvN25899;
Mon, 30 May 2005 09:18:57 -0600 (MDT)
Message-Id: <200505301518.j4UFIvN25899 [at] cs [dot] utep.edu>
Date: Mon, 30 May 2005 09:18:56 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: from NA Digest
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: go05 [at] dali [dot] ace.ual.es
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: uGQkzhY3KzlywwL0FUxUZA==
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
From: Global Optimization 2005
Date: Mon, 23 May 2005 14:25:29 +0200 (CEST)
Subject: Workshop in Spain on Global Optimization
Extended deadline for submitting abstracts Go05: May 31th, 2005
INTERNATIONAL WORKSHOP ON GLOBAL OPTIMIZATION GO05
http://www.ace.ual.es/~go05
Almeria, Spain, SEPTEMBER 18-22, 2005
Global Optimization, the field including theory, methods and applications
of optimization techniques aimed at detecting a global optimum for difficult
mathematical programming problems in which many local optima might exist,
is a rich area of research. The subject generates many papers published in
qualified scientific journals and books; a journal and a series of monographs
explicitly dedicated to the field exist now for more than a decade. Research
done
by PhD students, young researchers and seniors is scattered over the world
and we see GO applied in many scientific fields. The workshop aims at bringing
together researchers from various fields that are dealing with this topic.
Researchers that have been applying GO recently are invited explicitly to
present the questions they are working on and to interact with experienced
researchers in Global Optimization. The workshop is organised in single
stream sessions, in order to give all participants the opportunity to enjoy
each of the presentations. Accordingly, only a limited number of
contributions will be accepted.
Organising committee:
Emilio Carrizosa, Sevilla
Tibor Csendes, Szeged
Inmaculada Garcia, Almeria
Eligius Hendrix, Wageningen
Panos Pardalos, Florida
Local organisers:
Miguel Cobo
Leocadio Casado
Pilar Ortigosa
Boglarka Toth
Consolacion Gil
Raul Banos
Juana Redondo
From owner-reliable_computing [at] interval [dot] louisiana.edu Mon May 30 10:29:54 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UFTsOI023945
for ; Mon, 30 May 2005 10:29:54 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4UFTswY023944
for reliable_computing-outgoing; Mon, 30 May 2005 10:29:54 -0500 (CDT)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4UFTjb4023940
for ; Mon, 30 May 2005 10:29:51 -0500 (CDT)
Received: from aragorn (aragorn [129.108.5.35])
by cs.utep.edu (8.11.7/8.11.7) with SMTP id j4UFRjQ25948;
Mon, 30 May 2005 09:27:45 -0600 (MDT)
Message-Id: <200505301527.j4UFRjQ25948 [at] cs [dot] utep.edu>
Date: Mon, 30 May 2005 09:27:44 -0600 (MDT)
From: Vladik Kreinovich
Reply-To: Vladik Kreinovich
Subject: Fwd: More Accurate Computation at ACM-SAC 2006: Call For Papers.
To: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Cc: isabelle.braems [at] lemhe [dot] u-psud.fr, langlois@univ-perp.fr
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: OfRKYjgX2YePeafMJEwwBQ==
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
forwarding. Vladik
------------- Begin Forwarded Message -------------
Apologies for multiple copies.
--
How to manage the need for more accurate and reliable results without
suffering from an impractical over-cost?
Next 2006 ACM Symposium on Applied Computing (Dijon, France, April
23-27, 2006) includes a special track about:
More Accurate Computation: Methods and Software.
This track focuses on today and tomorrow methods and software to go
farther than the precision currently available on our computers. It
aims to gather applied computer scientists, computer engineers and
application developers together with researchers on numerical software
quality to exhibit the current state of the art on the need and the
solutions to reach both accuracy, reliability and performance in
software.
Call for papers:
Authors are invited to submit papers related to accuracy, reliability
and performance in numerical software. Specific issues to be addressed
include:
* Alternatives to provide accuracy, reliability and performance
o Hardware facilities: fused-multiply and add, long accumulators,...
o Software for an extended precision: multiprecision libraries,
arbitrary or fixed-length expansions,...
o Accurate algorithms: error free transformations, data structure
driven algorithms,...
o Reliable software: guaranteed accuracy, rigorous bounds, interval
arithmetic, formal methods,...
* Applications that need accuracy, reliability and performance
o Mathematical Software: elementary functions, constant
computations, symbolic computation, number theory,...
o Computational Geometry, Robotics, Scientific Computing,...
Important due dates:
o September 1, 2005: Abstract due
o September 3, 2005: Paper submissions
o October 15, 2005: Author notification
o November 5, 2005: Camera-Ready copy
URL: More information is available at
http://webdali.univ-perp.fr/mcms
Organizers:
* Philippe Langlois, University of Perpignan, France.
langlois@univ-perp.fr
* Siefried M. Rump, Technical University Hamburg-Harburg, Germany.
rump@tu_harburg.de
--
Philippe LANGLOIS
Universite de Perpignan, France.
Phone: +33 (0) 468 662 135
http://webdali.univ-perp.fr/~langlois
------------- End Forwarded Message -------------
From owner-reliable_computing [at] interval [dot] louisiana.edu Tue May 31 10:00:51 2005
Received: from interval.louisiana.edu (daemon@localhost [127.0.0.1])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4VF0prG025882
for ; Tue, 31 May 2005 10:00:51 -0500 (CDT)
Received: (from daemon@localhost)
by interval.louisiana.edu (8.13.1/8.13.1/Submit) id j4VF0pGb025881
for reliable_computing-outgoing; Tue, 31 May 2005 10:00:51 -0500 (CDT)
Received: from pickering.cc.nd.edu (pickering.cc.nd.edu [129.74.250.225])
by interval.louisiana.edu (8.13.1/8.13.1/ull-interval-math-majordomo-1.5) with ESMTP id j4VF0f8m025877
for ; Tue, 31 May 2005 10:00:47 -0500 (CDT)
Received: from darwin.helios.nd.edu (darwin.helios.nd.edu [129.74.250.114])
by pickering.cc.nd.edu (Switch-3.1.7/Switch-3.1.7) with ESMTP id j4VEwbmm015602
(version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO);
Tue, 31 May 2005 09:58:38 -0500 (EST)
Date: Tue, 31 May 2005 09:58:39 -0500 (EST)
From: Mark Stadtherr
Reply-To: Mark Stadtherr
To: Vladik Kreinovich
cc: reliable_computing [at] interval [dot] louisiana.edu, interval [at] cs [dot] utep.edu
Subject: Re: from SIAM Review
In-Reply-To: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu>
Message-ID:
References: <200505271632.j4RGW4A09294 [at] cs [dot] utep.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-ND-MTA-Date: Tue, 31 May 2005 09:58:43 -0500 (EST)
X-ND-Virus-Scan: engine v4.4.00; dat v4502
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk
Just to add briefly to the discussion of this "challenge" problem --
In my group we have been using this as a demonstration/test
problem since 2002 (http://www.nd.edu/~markst/ind2002/slides249e.pdf)
There are some published results/discussion in
Y. Lin and M. A. Stadtherr, J. Global Optimization, 29, 281-296 (2004).
(preprint at http://www.nd.edu/~markst/ydl2004a.pdf)
For another "toy" problem with a very large number of local
minima (on the order of ten billion for a six-variable case),
people might consider using "Siirola's Problem." This is
Problem 4 in the paper cited above, and there are some additional
results at http://www.nd.edu/~markst/slides-rec04.pdf, or in
Y. Lin and M. A. Stadtherr, Industrial & Engineering Chemistry
Research, 43, 3741-3749 (2004).
(preprint at http://www.nd.edu/~markst/ydl2004b.pdf)
Mark
========================================
Mark A. Stadtherr
Professor
Department of Chemical and Biomolecular Engineering
University of Notre Dame
Notre Dame, IN 46556
Phone: (574) 631-9318
Fax: (574) 631-8366
Email: markst [at] nd [dot] edu
========================================
On Fri, 27 May 2005, Vladik Kreinovich wrote:
> Dear Friends,
>
> This is just FYI.
>
> The lastest June 2005 issue of SIAM Review (Vol. 47, No. 2) has a review of the
> SIAM 100-Digit Challenge book (SIAM, 2004) by Nicholas J. Higham, who says:
>
> "Wagon's chapter "Think Globally, Act Locally shows how interval analysis can
> be used to solve a gloabl minimization problem in two variables; in doing so it
> provides the best summary of the benefits of interval analysis that I have
> seen"
>
> Vladik
>
> P.S. I check with Google, a version of this chapter is posted on
> www-m8.mathematik.tu-muenchen.de/ m3/ftp/Bornemann/pdf/chap4.pdf
>
>