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