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