From owner-reliable_computing Fri Aug 1 08:00:45 1997
Received: by interval.usl.edu id AA02663
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 1 Aug 1997 15:00:58 -0500
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA02657
(5.65c/IDA-1.4.4 for ); Fri, 1 Aug 1997 15:00:54 -0500
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA05925; Fri, 1 Aug 97 14:00:45 MDT
Date: Fri, 1 Aug 97 14:00:45 MDT
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9708012000.AA05925 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu, interval [at] cs [dot] utep.edu
Subject: Robot success repeated
Sender: owner-reliable_computing
Precedence: bulk
A modified version of the University of Texas at El Paso's
interval-based robot Diablo (that won 3rd
place in last year's International 1996 AAAI Robot Competition)
has now won first place at the AAAI-97
International Robot Competition. The
winning team included Luis Floriano (team leader),
Chitta Baral (faculty advisor), Arron Hardesty, Monica Nogueira, and
Tran Cao Son.
The International Robot Competition is an annual event organized by the
American Association for Artifical Intelligence (AAAI). This year's
competition was held in Providence, Rhode Island. The robots were supposed
to use a vacuum cleaner to tidy up a room.
Congratulations to the winners!
From owner-reliable_computing Thu Aug 7 18:58:59 1997
Received: by interval.usl.edu id AA06088
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Thu, 7 Aug 1997 09:59:41 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA06082
(5.65c/IDA-1.4.4 for ); Thu, 7 Aug 1997 09:59:32 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id QAA04585; Thu, 7 Aug 1997 16:58:59 +0200 (MET DST)
Date: Thu, 7 Aug 1997 16:58:59 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708071458.QAA04585 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Linear systems depending on interval parameters
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
I have just subscribed to the list.
More information about me can be found on my WWW pages
(see the signature below).
It so happens that the problem, as described by the message below:
>
> >From "Franck DELCROIX" Franck.DELCROIX [at] devinci [dot] fr Tue Jun 24 03:14:01 1997
>
> My question concerns the solution of linear systmes of equations
> with interval coefficients.
>
> Let's consider a linear system AX=B where Aij and Bi coefficients are
> functions of N interval variables. That is :
>
> A(y1,...,yN) X = B(y1,...,yN) (1)
>
> - Solving (1) for X is possible in some (rare) cases using methods
> presented in "classical" interval litterature (e.g. Alefeld, Hansen, ...)
>
[...]
>
> - But, I recently read a paper where they consider the N-dimensional volume
> defined by the 2*N end-points of the interval (y1,...,yN).
> Then they solve classically AX=B for the 2^N possible realisations
> and sort the answers.
> Hence, X is [min(Xi) ; max(Xi)] where i stands for one of the
> realisations amongst the 2^N possible combinations of the 2*N end-points.
>
... is also my problem, more or less.
BTW: Can you, Franck, give the reference to the above mentioned paper?
As Markov pointed out (with which I strongly agree):
> From: "Svetoslav Markov"
>
> My comments are related to this problem, which seems to be
> a very important problem from applicational point of view.
> ---------------------------------------------------------
However, from Markov's further text and other answers I understand
that in general it is not yet solved, except for some very simple
or special cases.
And it might seem, from the letter by Vladik Kreinovich:
> From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
>
> The extreme complexity of this problem in general can be proven by the
> fact that an arbitrary algebraic set can be represented as a set of all
> possible solution of an appropriate linear systems with coefficients
> linearly depending on interval variables. For a proof, see:
>
> G\"otz Alefeld, Vladik Kreinovich, and G\"unter Mayer,
> ``The Shape of the Solution Set for Systems of Interval Linear Equations
> with Dependent Coefficients'', Mathematische Nachrichten (to appear).
>
... that it even may be not solvable in general...
Therefore I would greatly appreciate obtaining references
(prefereably with full bibliographical data) to all works
on this subject. May be something relevant for my
particular application shows up anyway.
Another problem, related to that (it even seems that
some of the respondents to the original question confused it
with the "dependence on interval parameters" problem)
I am addressing in a separate letter.
Best regards,
-- Zenon Kulpa
_______________________________________________________________
Dr. Zenon Kulpa |
Center of Mechanics, | Whatever we may want to say,
Institute of Fundamental | we probably won't say
Technological Research | exactly that.
ul. Swietokrzyska 21 |
00-049 Warszawa, POLAND | Marvin Minsky
______________________________|________________________________
tel ++48-22/826-1281 ext 279 fax ++48-22/826-9815
URL http://www.ippt.gov.pl/~zkulpa
_______________________________________________________________
From owner-reliable_computing Thu Aug 7 19:46:49 1997
Received: by interval.usl.edu id AA06411
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Thu, 7 Aug 1997 10:47:29 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA06405
(5.65c/IDA-1.4.4 for ); Thu, 7 Aug 1997 10:47:23 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id RAA04617; Thu, 7 Aug 1997 17:46:49 +0200 (MET DST)
Date: Thu, 7 Aug 1997 17:46:49 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708071546.RAA04617 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
During the recent discussion on the problem of
linear systems depending on interval parameters,
some of the respondents mentioned another, simpler
but related problem.
Namely, in several papers on applications of linear interval
systems of equations (e.g., Rao & Berke, AIAA Journal 35(4), 1997)
I have found an approach (called "combinatorial") for finding
tight (outer) interval enclosure for the set of solutions
of the linear system Ax = b with interval coefficients (in A and b).
It consists of solving all 2^m real systems A'x = b' where
A' and b' are build as all possible combinations of endpoints
of the interval elements of A and b (m being the number
of thick interval elements of A and b). The papers claim that
for linear systems the Max and Min of the set of solutions
so obtained gives the tightest possible (outer) enclosure for
the set of solutions of the original interval system.
Despite its exponential complexity, the method, if correct,
is useful in practice, e.g. as a reference method for testing
other solution methods (at least for sufficiently small systems ;-).
However, in none of these papers I have found the proof
of correctness of the method, or a reference to the paper
containing one. Also, the basic textbooks on the subject
(e.g., Alefeld & Herzberger 1983, Neumaier 1990) do not even
mention this approach as a possibility! The Alefeld & Herzberger
book discusses a somewhat similar method (attributed to Kuperman & Hansen).
>From the description of that method I became suspicious
as to the correctness of the combinatorial approach.
Of course, it is true, as pointed out by Vladik Kreinovich:
> From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
>
> Not necessarily: e.g., for a single equation [-1,1]x=[0,1], the four
> points are 0, 1, and -1, so we should expect the interval to be [-1,1],
> but in reality, possible values of x form the entire real line. It is
> easy to modify this result and make it non-trivial.
>
... that the method fails when A is singular.
It is easy to give lots of nontrivial examples for that.
However, what if A is regular?
I have tried to find a counterexample for 2x2 and 3x3 systems,
(with regular matrices) then explored these two cases analytically
(and diagrammatically - but this is another story) -
and it seems that for them the combinatorial approach is valid!
I have not made it yet into a rigorous proof (not being myself
a specialist in interval matrix theory...), but I have the feeling
it is quite possible. Does it generalize to n > 3, I wonder?
So, is the "combinatorial approach" valid for systems
of linear interval equations with regular matrix A?
Are there any definite answers/references/counterexamples?
Regards,
-- Zenon Kulpa
PS. [To Prof. Arnold Neumaier: in your book "Interval methods
for systems of equations" you wrote, on p. 169:
"Linear equations whose coefficient matrix depends
on parameters varying in specified intervals are
treated in Kelch (1988), Neumaier (1987d) and ...".
However, in the References there are no entries
with these signatures. Can you provide the correct
references? -- ZK ].
From owner-reliable_computing Thu Aug 7 09:34:26 1997
Received: by interval.usl.edu id AA06794
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Thu, 7 Aug 1997 12:34:51 -0500
Received: from po1.glue.umd.edu by interval.usl.edu with SMTP id AA06788
(5.65c/IDA-1.4.4 for ); Thu, 7 Aug 1997 12:34:43 -0500
Received: from espresso.eng.umd.edu (muhannar [at] espresso [dot] eng.umd.edu [129.2.103.26])
by po1.glue.umd.edu (8.8.7/8.8.7) with ESMTP id NAA23496;
Thu, 7 Aug 1997 13:34:32 -0400 (EDT)
Received: from localhost (muhannar@localhost)
by espresso.eng.umd.edu (8.8.7/8.8.7) with SMTP id NAA04182;
Thu, 7 Aug 1997 13:34:27 -0400 (EDT)
X-Authentication-Warning: espresso.eng.umd.edu: muhannar owned process doing -bs
Date: Thu, 7 Aug 1997 13:34:26 -0400 (EDT)
From: Rafi Muhanna
X-Sender: muhannar [at] espresso [dot] eng.umd.edu
To: Zenon Kulpa
Cc: reliable_computing [at] interval [dot] usl.edu
Subject: Re: Linear interval systems: "combinatorial" approach
In-Reply-To: <199708071546.RAA04617 [at] zmit1 [dot] ippt.gov.pl>
Message-Id:
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-reliable_computing
Precedence: bulk
I would like to mention that the combinatorial approach for solution of
linear interval systems of equations with interval coefficients(in A and
b, and A is not-singular) is a correct one, we have used this approach
(as a natural understanding of the problems we delt with) as a reference
solution to evaluate our results of applying interval arithmetic
in mechanics problems. I can refere to the following publications:
Muhanna, Rafi L., Mullen, Robert L. "Development of Interval Based Methods
for Fuzziness in Continuum Mechanics, " ISUMA-NAFIPS'95, 145-150,
September 17-20, 1995.
Mullen, Robert L., Muhanna, Rafi L. "Structural Analysis with Fuzzy-Based
Load Uncertainty, " 7th ASCE EMD/STD Joint Specialty Conference on
Probabilistic Mechanics and Structural Reliability, WP I, MA, pp 310-313,
August 7-9, 1996
Rafi L. Muhanna
On Thu, 7 Aug 1997, Zenon Kulpa wrote:
> During the recent discussion on the problem of
> linear systems depending on interval parameters,
> some of the respondents mentioned another, simpler
> but related problem.
>
> Namely, in several papers on applications of linear interval
> systems of equations (e.g., Rao & Berke, AIAA Journal 35(4), 1997)
> I have found an approach (called "combinatorial") for finding
> tight (outer) interval enclosure for the set of solutions
> of the linear system Ax = b with interval coefficients (in A and b).
> It consists of solving all 2^m real systems A'x = b' where
> A' and b' are build as all possible combinations of endpoints
> of the interval elements of A and b (m being the number
> of thick interval elements of A and b). The papers claim that
> for linear systems the Max and Min of the set of solutions
> so obtained gives the tightest possible (outer) enclosure for
> the set of solutions of the original interval system.
>
> Despite its exponential complexity, the method, if correct,
> is useful in practice, e.g. as a reference method for testing
> other solution methods (at least for sufficiently small systems ;-).
>
> However, in none of these papers I have found the proof
> of correctness of the method, or a reference to the paper
> containing one. Also, the basic textbooks on the subject
> (e.g., Alefeld & Herzberger 1983, Neumaier 1990) do not even
> mention this approach as a possibility! The Alefeld & Herzberger
> book discusses a somewhat similar method (attributed to Kuperman & Hansen).
> From the description of that method I became suspicious
> as to the correctness of the combinatorial approach.
> Of course, it is true, as pointed out by Vladik Kreinovich:
>
> > From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
> >
> > Not necessarily: e.g., for a single equation [-1,1]x=[0,1], the four
> > points are 0, 1, and -1, so we should expect the interval to be [-1,1],
> > but in reality, possible values of x form the entire real line. It is
> > easy to modify this result and make it non-trivial.
> >
> ... that the method fails when A is singular.
> It is easy to give lots of nontrivial examples for that.
> However, what if A is regular?
>
> I have tried to find a counterexample for 2x2 and 3x3 systems,
> (with regular matrices) then explored these two cases analytically
> (and diagrammatically - but this is another story) -
> and it seems that for them the combinatorial approach is valid!
> I have not made it yet into a rigorous proof (not being myself
> a specialist in interval matrix theory...), but I have the feeling
> it is quite possible. Does it generalize to n > 3, I wonder?
>
> So, is the "combinatorial approach" valid for systems
> of linear interval equations with regular matrix A?
> Are there any definite answers/references/counterexamples?
>
> Regards,
>
> -- Zenon Kulpa
>
> PS. [To Prof. Arnold Neumaier: in your book "Interval methods
> for systems of equations" you wrote, on p. 169:
> "Linear equations whose coefficient matrix depends
> on parameters varying in specified intervals are
> treated in Kelch (1988), Neumaier (1987d) and ...".
> However, in the References there are no entries
> with these signatures. Can you provide the correct
> references? -- ZK ].
>
-------------------------------------------------------------------------
Rafi L. Muhanna
Department of Civil Engineering (301) 405-7965 (VOICE)
University of Maryland at College Park (301) 405-2585 (FAX)
College Park, MD 20742, USA. muhannar [at] eng [dot] umd.edu
From owner-reliable_computing Thu Aug 7 21:49:05 1997
Received: by interval.usl.edu id AA07050
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Thu, 7 Aug 1997 12:49:49 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA07044
(5.65c/IDA-1.4.4 for ); Thu, 7 Aug 1997 12:49:38 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id TAA04732; Thu, 7 Aug 1997 19:49:05 +0200 (MET DST)
Date: Thu, 7 Aug 1997 19:49:05 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708071749.TAA04732 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Rafi Muhanna
>
> I would like to mention that the combinatorial approach for solution of
> linear interval systems of equations with interval coefficients(in A and
> b, and A is not-singular) is a correct one, we have used this approach
> (as a natural understanding of the problems we delt with) as a reference
> solution to evaluate our results of applying interval arithmetic
> in mechanics problems.
>
Nice to hear that. We did the same (until doubts creeped in... ;-).
However, do you have a correctness proof, or a reference to one?
Regards,
-- Zenon Kulpa
From owner-reliable_computing Fri Aug 8 04:42:43 1997
Received: by interval.usl.edu id AA07939
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 8 Aug 1997 09:42:46 -0500
Received: by interval.usl.edu id AA07929
(5.65c/IDA-1.4.4 for reliable_computing); Fri, 8 Aug 1997 09:42:43 -0500
Date: Fri, 8 Aug 1997 09:42:43 -0500
From: "Kearfott R. Baker"
Message-Id: <199708081442.AA07929 [at] interval [dot] usl.edu>
To: reliable_computing
Subject: NEW DEADLINE FOR SUBMISSION CP97 Workshop on Constraint Reasoning on the INTERNET
Sender: owner-reliable_computing
Precedence: bulk
Note from the list maintainer:
This message, like a number of others, "bounced" because the header
field (CC list) was too long. In future, I will not guarantee I will
fix and forward all such messages. I thank you for your cooperation.
Best regards,
R. Baker Kearfott
----- Begin Included Message -----
From owner-reliable_computing Fri Aug 8 05:23:41 1997
Date: Fri, 8 Aug 1997 05:23:40 -0500
To: owner-reliable_computing [at] interval [dot] usl.edu
From: owner-reliable_computing
Subject: BOUNCE reliable_computing [at] interval [dot] usl.edu: Header field too long (>1024)
Content-Length: 5662
From: Thom Fruehwirth
Date: Fri, 8 Aug 97 12:15:54 +0200
To: Thom Fruehwirth
Subject: NEW DEADLINE FOR SUBMISSION CP97 Workshop on Constraint Reasoning on
the Internet
Cc: lp-internet [at] doc [dot] ic.ac.uk, eapls [at] mailbase [dot] ac.uk, clpr-users [at] iscs [dot] nus.sg,
ccl [at] dfki [dot] uni-sb.de, atp_alias [at] cs [dot] jcu.edu.au,
flp_ws_maillist [at] issan [dot] informatik.uni-dortmund.de,
alp-list [at] intellektik [dot] informatik.th-darmstadt.de, cclp.x [at] parc [dot] xerox.com,
clean-list [at] cs [dot] kun.nl, rewriting [at] loria [dot] fr, compunode [at] ecrc [dot] de,
quintus-users [at] quintus [dot] com, sicstus-users [at] sics [dot] se, life-users [at] cs [dot] sfu.ca,
clp [at] cis [dot] ohio-state.edu, flprog [at] informatik [dot] uni-muenchen.de,
lprolog [at] central [dot] cis.upenn.edu, gulp [at] di [dot] unipi.it,
g-ganzinger@mpi-sb.mpg.de, haskell [at] dcs [dot] gla.ac.uk,
fg121 [at] bach [dot] informatik.uni-ulm.de, idss [at] socs [dot] uts.edu.au,
igpl [at] doc [dot] ic.ac.uk, ikbs [at] caad [dot] ed.ac.uk, jicslp96 [at] informatik [dot] uni-bonn.de,
kr94 [at] mail2 [dot] ai.univie.ac.at, lics-email [at] cs [dot] indiana.edu,
lics [at] research [dot] bell-labs.com, linear [at] cs [dot] stanford.edu,
logic [at] theory [dot] lcs.mit.edu, lppnmr [at] cs [dot] engr.uky.edu, mlnet [at] swi [dot] psy.uva.nl,
mrg [at] itc [dot] it, nl-kr [at] cs [dot] rpi.edu, parforce [at] ecrc [dot] de,
prolia [at] tlxf [dot] geomail.org, prolog-pe [at] bach [dot] ces.cwru.edu,
prolog-vendors [at] sics [dot] se, prolog [at] mch [dot] sni.de, prolog [at] sunbim [dot] be,
reliable_computing [at] interval [dot] usl.edu, semantics-list [at] newton [dot] cam.ac.uk,
sgaico [at] cui [dot] unige.ch, skeletons [at] dcs [dot] ed.ac.uk,
theorem-provers [at] ai [dot] mit.edu, theory-a [at] vm1 [dot] nodak.edu,
theorynt [at] ndsuvm1 [dot] intellektik.informatik.th-darmstadt.de,
types [at] dcs [dot] glasgow.ac.uk, fg214 [at] informatik [dot] uni-kiel.d400.de
References: <199706251137.NAA05086 [at] phaethon [dot] pst.informatik.uni-muenchen.de>
<199708040926.LAA04978@pst3>
THIRD CALL FOR PAPERS - NEW DEADLINE: AUGUST 17!
CP97 Workshop on Constraint Reasoning on the Internet
Schloss Hagenberg, Austria, 1 November 1997
The half-day workshop will be held in conjunction with the Third
International Conference on Principles and Practice of Constraint
Programming (CP97), October 29 - November 1, 1997
SCOPE OF THE WORKSHOP
Constraint reasoning has proven its merits in a variety of application
areas including decision support systems. The goal of the workshop is
to assess whether and in what way constraint reasoning and programming
may be applied to developing intelligent applications for the Web
including agent-based systems.
We believe that constraint-based programming will be essential for
intelligent internet applications, be they called intelligent
information systems, intelligent agents, etc. The reason is that since
constraints can express and deal with partial information, they
address some of the essential issues of intelligent applications on
the WWW:
- Internet applications are likely to be distributed and thus,
locally, complete information may not be available at all times.
- The internet user may not be able to give all the necessary input,
but still expect to get some answer.
- The internet user may not want to reveal all he knows to an application
for security or privacy reasons.
Topics of interest include, but are not limited to:
- internet applications
- intelligent agents
- WWW interfaces, interactivity
- user-specific content presentation, on-the-fly web page creation
- CLP-applets and internet libraries - what do existing LP libraries offer?
- internet information search, data mining and information retrieval
- decision support systems that can/should be put on the internet
- concurreny and distributed computing w.r.t. internet
Papers that combine theory and practice are especially welcome.
PAPER SUBMISSIONS
Submission deadline is 17 August 1997. Authors are invited to submit
original papers written in English with up to 10 A4 pages by
electronic mail in self-contained uuencoded Postscript format to Thom
Fruehwirth at fruehwir [at] informatik [dot] uni-muenchen.de. Decisions on
acceptance will be sent to authors by 19 September 1997.
PUBLICATION
An informal proceedings of the workshop will be available to the
workshop participants. Final copies will be due by 5 October 1997.
ORGANISATION
Thom Fruehwirth, LMU Munich, Germany, fruehwir [at] informatik [dot] uni-muenchen.de
Manuel Hermengildo, Univ. Politecnica de Madrid, Spain, herme [at] fi [dot] upm.es
Paul Tarau, Univ. de Moncton, Canada, tarau [at] info [dot] umoncton.ca
Philippe Codognet, INRIA, France, Philippe.Codognet [at] inria [dot] fr
Francesca Rossi, Univ. di Pisa, Italy, rossi [at] di [dot] unipi.it
IMPORTANT DATES
17 August 1997: Paper submissions (by email only)
19 September 1997: Acceptance decisions
5 October 1997: Final copy due
1 November 1997: Workshop
FURTHER INFORMATION
This and more information related to the topic of the workshop
may be found in the internet at URL:
http://www.pst.informatik.uni-muenchen.de/personen/fruehwir/wcicp97.html
----- End Included Message -----
From owner-reliable_computing Fri Aug 8 06:15:36 1997
Received: by interval.usl.edu id AA08385
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 8 Aug 1997 15:16:56 -0500
Received: from mercury.Sun.COM by interval.usl.edu with SMTP id AA08379
(5.65c/IDA-1.4.4 for ); Fri, 8 Aug 1997 15:16:46 -0500
Received: from Eng.Sun.COM ([129.146.1.25]) by mercury.Sun.COM (SMI-8.6/mail.byaddr) with SMTP id NAA16425; Fri, 8 Aug 1997 13:15:51 -0700
Received: from gww.eng.sun.com by Eng.Sun.COM (SMI-8.6/SMI-5.3)
id NAA23985; Fri, 8 Aug 1997 13:15:49 -0700
Received: by gww.eng.sun.com (SMI-8.6/SMI-SVR4)
id NAA14147; Fri, 8 Aug 1997 13:15:36 -0700
Date: Fri, 8 Aug 1997 13:15:36 -0700
From: Bill.Walster [at] eng [dot] sun.com (William Walster)
Message-Id: <199708082015.NAA14147 [at] gww [dot] eng.sun.com>
To: zkulpa [at] zmit1 [dot] ippt.gov.pl
Subject: Re: FYI: Linear interval systems: "combinatorial" approach
Cc: reliable_computing [at] interval [dot] usl.edu
X-Sun-Charset: US-ASCII
Sender: owner-reliable_computing
Precedence: bulk
Here is a proof I received from Eldon Hansen.
Regards,
Bill Walster
----- Begin Included Message -----
William Walster wrote:
>
> ----- Begin Included Message -----
>
> >From zkulpa [at] zmit1 [dot] ippt.gov.pl Thu Aug 7 08:52:17 1997
> Date: Thu, 7 Aug 1997 17:46:49 +0200 (MET DST)
> From: Zenon Kulpa
> To: reliable_computing [at] interval [dot] usl.edu
> Subject: Linear interval systems: "combinatorial" approach
> Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
>
> During the recent discussion on the problem of
> linear systems depending on interval parameters,
> some of the respondents mentioned another, simpler
> but related problem.
>
> Namely, in several papers on applications of linear interval
> systems of equations (e.g., Rao & Berke, AIAA Journal 35(4), 1997)
> I have found an approach (called "combinatorial") for finding
> tight (outer) interval enclosure for the set of solutions
> of the linear system Ax = b with interval coefficients (in A and b).
> It consists of solving all 2^m real systems A'x = b' where
> A' and b' are build as all possible combinations of endpoints
> of the interval elements of A and b (m being the number
> of thick interval elements of A and b). The papers claim that
> for linear systems the Max and Min of the set of solutions
> so obtained gives the tightest possible (outer) enclosure for
> the set of solutions of the original interval system.
>
> Despite its exponential complexity, the method, if correct,
> is useful in practice, e.g. as a reference method for testing
> other solution methods (at least for sufficiently small systems ;-).
>
> However, in none of these papers I have found the proof
> of correctness of the method, or a reference to the paper
> containing one. Also, the basic textbooks on the subject
> (e.g., Alefeld & Herzberger 1983, Neumaier 1990) do not even
> mention this approach as a possibility! The Alefeld & Herzberger
> book discusses a somewhat similar method (attributed to Kuperman & Hansen).
> >From the description of that method I became suspicious
> as to the correctness of the combinatorial approach.
> Of course, it is true, as pointed out by Vladik Kreinovich:
>
> > From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
> >
> > Not necessarily: e.g., for a single equation [-1,1]x=[0,1], the four
> > points are 0, 1, and -1, so we should expect the interval to be [-1,1],
> > but in reality, possible values of x form the entire real line. It is
> > easy to modify this result and make it non-trivial.
> >
> ... that the method fails when A is singular.
> It is easy to give lots of nontrivial examples for that.
> However, what if A is regular?
>
> I have tried to find a counterexample for 2x2 and 3x3 systems,
> (with regular matrices) then explored these two cases analytically
> (and diagrammatically - but this is another story) -
> and it seems that for them the combinatorial approach is valid!
> I have not made it yet into a rigorous proof (not being myself
> a specialist in interval matrix theory...), but I have the feeling
> it is quite possible. Does it generalize to n > 3, I wonder?
>
> So, is the "combinatorial approach" valid for systems
> of linear interval equations with regular matrix A?
> Are there any definite answers/references/counterexamples?
>
> Regards,
>
> -- Zenon Kulpa
>
> PS. [To Prof. Arnold Neumaier: in your book "Interval methods
> for systems of equations" you wrote, on p. 169:
> "Linear equations whose coefficient matrix depends
> on parameters varying in specified intervals are
> treated in Kelch (1988), Neumaier (1987d) and ...".
> However, in the References there are no entries
> with these signatures. Can you provide the correct
> references? -- ZK ].
>
> ----- End Included Message -----
Bill:The "combinatorial" method is valid if the matrix is regular. I'll
outline a proof:
Write the problem as [A,B]x=[a,b]. Consider the first orthant. Since
each component of x is non-negative, we can write the equation as
[Ax,Bx]=[a,b].For a solution to exist, the intevals on the two sides of
the equation must intersect. Therefore, either (1) Ax<=b or (2)Bx>=a.To
get the interval solution in the first orthant, we can solve linear
programming problems such as max xi subject to condtions (1) and (2) and
the condition x>0 (since we are in the positive orthant). The solution
will be at a vertex of the feasible region. It can be obtained by
solving the equations formed by the appropriate rows from (1) and (2)
and or equations of the form xj=0. If no equation of the form xj=0 is
active at the solution, then the solution is one of the "combinatorial"
solutions. If an equation xj=0 is active, then the solution region will
extend across the hyperplane xj=0 and a larger (when maximizing xi)
value of xi will be obtained in the orthant across the xj=0 boundary.
Repeating this argument, the extreme values of each xi occur at solution
of sytems made up of rows from relations such as (1) and (2). The
"combinatiorial" solution contains all such solutions so it yields a
correct solution.
The difficulty with the singular case is that the combinatorial
solution can give the exterior of the solution. Consider Kreinovich's
scalar example [-1,1]x=[0,1]. For x>=0, we have [-x,x]=[0,1]. For the
intervals to overlap, we need -x<=1 or x>=0 so at least x>=0. For x<=0,
we have [x, -x]=[0,1] so x<=1 or -x>=0. The combined result is the
entire real line. The candidate combinatorial solutions are -0 and +0.
The solution is the the exterior of the these points instead of the
interior.
----- End Included Message -----
From owner-reliable_computing Sat Aug 9 17:48:07 1997
Received: by interval.usl.edu id AA08843
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 9 Aug 1997 08:48:44 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA08837
(5.65c/IDA-1.4.4 for ); Sat, 9 Aug 1997 08:48:38 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IM8OZE1N2OE0RHQB [at] Pap [dot] UniVie.AC.AT>; Sat, 09 Aug 1997 15:47:24 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA28995; Sat, 09 Aug 1997 15:48:07 +0200
Date: Sat, 09 Aug 1997 15:48:07 +0200
From: Arnold Neumaier
Subject: Re: Linear interval systems: "combinatorial" approach
To: reliable_computing [at] interval [dot] usl.edu, zkulpa [at] zmit1 [dot] ippt.gov.pl
Cc: zkulpa [at] zmit1 [dot] ippt.gov.plneum
Message-Id: <9708091348.AA28995 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
Zenon Kulpa asks about the validity of:
>>an approach (called "combinatorial") for finding
tight (outer) interval enclosure for the set of solutions
of the linear system Ax = b with interval coefficients (in A and b).
It consists of solving all 2^m real systems A'x = b' where
A' and b' are build as all possible combinations of endpoints
of the interval elements of A and b (m being the number
of thick interval elements of A and b)....
However, in none of these papers I have found the proof
of correctness of the method, or a reference to the paper
containing one. Also, the basic textbooks on the subject
(e.g., Alefeld & Herzberger 1983, Neumaier 1990) do not even
mention this approach as a possibility!<<
Chapter 6 of my book (Neumaier 1990) discusses Rohn's Theory and
contains in Theorem 6.2.2 a justification of this method, with a
useful refinement to restrict the number of systems that need to be solved.
Rohn's sign-accord algorithm further reduces the work. The method is
useful for system of dimension up to about 10, or when there are
strong sign restrictions known.
Arnold Neumaier
From owner-reliable_computing Sat Aug 9 21:56:59 1997
Received: by interval.usl.edu id AA09193
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 9 Aug 1997 12:57:38 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA09187
(5.65c/IDA-1.4.4 for ); Sat, 9 Aug 1997 12:57:32 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id TAA06356; Sat, 9 Aug 1997 19:56:59 +0200 (MET DST)
Date: Sat, 9 Aug 1997 19:56:59 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708091756.TAA06356 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu, neum [at] cma [dot] univie.ac.at
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Arnold Neumaier
>
> Zenon Kulpa asks about the validity of:
>
> >>an approach (called "combinatorial") for finding
> tight (outer) interval enclosure for the set of solutions
> of the linear system Ax = b with interval coefficients (in A and b).
> It consists of solving all 2^m real systems A'x = b' where
> A' and b' are build as all possible combinations of endpoints
> of the interval elements of A and b (m being the number
> of thick interval elements of A and b)....
> However, in none of these papers I have found the proof
> of correctness of the method, or a reference to the paper
> containing one. Also, the basic textbooks on the subject
> (e.g., Alefeld & Herzberger 1983, Neumaier 1990) do not even
> mention this approach as a possibility!<<
>
> Chapter 6 of my book (Neumaier 1990) discusses Rohn's Theory and
> contains in Theorem 6.2.2 a justification of this method, with a
> useful refinement to restrict the number of systems that need to be solved.
> Rohn's sign-accord algorithm further reduces the work. The method is
> useful for system of dimension up to about 10, or when there are
> strong sign restrictions known.
>
Thank you for for the information.
However, I may sound foolish, but I do not see the connection
of the contents of Chapter 6 with the "combinatorial" method.
The Theorem 6.2.2 says that every extremal point xe
of the set of solutions of A x = b satisfies some other equation,
namely inf(D(A xe - b)) = 0 for some real matrix D such that |D| = I
(as I understand that, D has only +1 or -1 at the main diagonal
and zeros elsewhere, and there are 2^n matrices of this kind,
where n x n is the size of A).
Moreover, the condition of the theorem states that b is a real
(not interval) vector [or is it a missprint? - the proof seems
to assume that b is an interval vector too].
The equation inf(D(A xe - b)) = 0 given in the Theorem 6.2.2
contains the original interval matrix A, and hence again
requires some interval solving method. Methods for solving
it are given further in Chapter 6: one is iterative
and requires computing interval enclosure of A^(-1),
the other is quite complicated also and in no clear
way resembles the "combinatorial" method outlined in my letter.
What it has to do with solving 2^m non-interval systems
of equations with all combinations of endpoints of intervals
contained in A (and b) as coefficients
[with m usually much larger than n]?.
So I am obviously missing something - would you be so kind
to explain where my understanding fails?
With best regards,
-- Zenon Kulpa
From owner-reliable_computing Sun Aug 10 14:05:16 1997
Received: by interval.usl.edu id AA09650
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sun, 10 Aug 1997 05:05:35 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA09644
(5.65c/IDA-1.4.4 for ); Sun, 10 Aug 1997 05:05:28 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IM9VHC1OVKE0RKTJ [at] Pap [dot] UniVie.AC.AT>; Sun, 10 Aug 1997 12:04:25 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA06901; Sun, 10 Aug 1997 12:05:16 +0200
Date: Sun, 10 Aug 1997 12:05:16 +0200
From: Arnold Neumaier
Subject: Re: Linear interval systems: "combinatorial" approach
To: neum [at] homer [dot] cma.univie.ac.at, reliable_computing [at] interval [dot] usl.edu,
zkulpa [at] zmit1 [dot] ippt.gov.pl
Message-Id: <9708101005.AA06901 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
Zenon Kulpa writes:
>>I do not see the connection
of the contents of Chapter 6 with the "combinatorial" method.
The Theorem 6.2.2 says that every extremal point xe
of the set of solutions of A x = b satisfies some other equation,
namely inf(D(A xe - b)) = 0 for some real matrix D such that |D| = I
(as I understand that, D has only +1 or -1 at the main diagonal
and zeros elsewhere, and there are 2^n matrices of this kind,
where n x n is the size of A).
Moreover, the condition of the theorem states that b is a real
(not interval) vector [or is it a missprint? - the proof seems
to assume that b is an interval vector too].
The equation inf(D(A xe - b)) = 0 given in the Theorem 6.2.2
contains the original interval matrix A, and hence again
requires some interval solving method. ...
What it has to do with solving 2^m non-interval systems
of equations with all combinations of endpoints of intervals
contained in A (and b) as coefficients
[with m usually much larger than n]?.
<<
b may be an interval vector; there is indeed a misprint.
For fixed diagonal +-1 matrix D, inf(D(A xe - b)) = 0 is rewritten as
a set of 2^n non-interval systems in equation (5b):
xe=Ae^{-1} be, where Ae=mid(A)-D rad(A) D', be=mid(b)+D rad(b)
for some diagonal +-1 matrix D'. Note that the coefficients of Ae
and be are endpoints of A and b. This gives a total of 2^{2n}
systems to solve. The results following Theorem 6.2.2 in my book
reduce this number further in case that an enclosure of A^{-1}
is known. The sign accord algorithm (p. 228) takes at worst also
2^{2n} systems to solve, but the work is usually less, and by use
of rank one updating techniques, solving each additional system
costs only O(n^2) work instead of O(n^3).
Arnold Neumaier
From owner-reliable_computing Sun Aug 10 21:44:08 1997
Received: by interval.usl.edu id AA09991
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sun, 10 Aug 1997 12:44:53 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA09985
(5.65c/IDA-1.4.4 for ); Sun, 10 Aug 1997 12:44:42 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id TAA06937; Sun, 10 Aug 1997 19:44:08 +0200 (MET DST)
Date: Sun, 10 Aug 1997 19:44:08 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708101744.TAA06937 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu, neum [at] cma [dot] univie.ac.at
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Arnold Neumaier
>
> >>I do not see the connection
> of the contents of Chapter 6 with the "combinatorial" method.
> The Theorem 6.2.2 says that every extremal point xe
> of the set of solutions of A x = b satisfies some other equation,
> namely inf(D(A xe - b)) = 0 for some real matrix D such that |D| = I
> (as I understand that, D has only +1 or -1 at the main diagonal
> and zeros elsewhere, and there are 2^n matrices of this kind,
> where n x n is the size of A).
> Moreover, the condition of the theorem states that b is a real
> (not interval) vector [or is it a missprint? - the proof seems
> to assume that b is an interval vector too].
> The equation inf(D(A xe - b)) = 0 given in the Theorem 6.2.2
> contains the original interval matrix A, and hence again
> requires some interval solving method. ...
> What it has to do with solving 2^m non-interval systems
> of equations with all combinations of endpoints of intervals
> contained in A (and b) as coefficients
> [with m usually much larger than n]?.
> <<
>
> b may be an interval vector; there is indeed a misprint.
>
Thank you - I have corrected it in my copy.
> For fixed diagonal +-1 matrix D, inf(D(A xe - b)) = 0 is rewritten as
> a set of 2^n non-interval systems in equation (5b):
> xe=Ae^{-1} be, where Ae=mid(A)-D rad(A) D', be=mid(b)+D rad(b)
> for some diagonal +-1 matrix D'. Note that the coefficients of Ae
> and be are endpoints of A and b.
>
Yes, now I see.
Note, however, that (5b) requires additional condition: D'xe >= 0.
It is not clear to me how this condition affects the argument
(and how to test it _before_ we calculated xe from (5b)? ).
Does it mean that if it so happens that the condition is
not satisfied, the calculation of xe by means of (5a) is not valid?
Then, how to find this particular xe?
Or can we miss some necessary xe in this way, hence obtaining
wrong bounds for the set of solutions?
> This gives a total of 2^{2n}
> systems to solve. The results following Theorem 6.2.2 in my book
> reduce this number further in case that an enclosure of A^{-1}
> is known. The sign accord algorithm (p. 228) takes at worst also
> 2^{2n} systems to solve, but the work is usually less, and by use
> of rank one updating techniques, solving each additional system
> costs only O(n^2) work instead of O(n^3).
>
Indeed, it seems that the Theorem 6.2.2 and further considerations
of Chapter 6 lead to conlusions justifying the "combinatorial" algorithm.
Thank you very much for the trouble of explaining the connection.
However, I would like to add some additional comments
(and complaints ;-):
- The resulting algorithm (for brevity, let us call it RN in the sequel)
is rather complicated, and quite unclearly described,
at least for somebody, like me, who is not a professional
mathematician and wants only to apply some mathematical results
in his area of application.
For me, after browsing through Chapter 6, it was just another
theoretical exercise not worth (sorry ;-) of hard work to understand
in all necessary details and to implement, as the result will be
still an exponential-complexity algorithm but much more complicated
(so it seemed) than the simple "combinatorial" one (provided
the latter can be proven valid).
- The RN algorithm, at least superficially, does not look as related
to the "combinatorial" one. At least I have had trouble to see
the connection without additional explanations, and it seems all
the authors of papers using the "combinatorial" algorithm
I have found have had the same problem with seeing the connection,
as they did not include a reference to your book or Rohn's paper
while describing the "combinatorial" algorithm (nor they used
its seemingly more efficient version as described in your book).
Certainly, the contents of Chapter 6 does not qualify,
without further explanations and argument, as a proof or
justification for the "combinatorial" algorithm in its
usual, common-sense version as described in my letter.
- The "combinatorial" algorithm is conceptually very simple
and easy to implement, and its complexity depends exponentially
on the actual number m of (thick) intervals in the matrix
(with m anywhere between 1 and n^2+n), whereas the RN
algorithm is much more complicated and has a complexity
exponential with 2n (and it could be that 2^m << 2^(2n)
for large systems with small number of interval coefficients(*),
or vice versa for systems with many interval coefficients).
Thus, the two algorithms, though closely related
(after careful inspection), are not truly interchangeable,
especially in practical applications.
(*) It is true that for systems with small number of interval
coefficients the number of systems to solve may be smaller
than 2^(2n) since for some different D and D' the resulting
matrix Ae (and vector be) may become identical.
It seems that the question of justifying the "combinatorial"
algorithm properly still deserves some clarifying publication
or a Section in some forthcoming textbook on interval algebra.
And, finally, a METAREMARK:
--------------------------
I have observed many times that practically all books
written by mathematicians on their subjects of study
are written for another professional mathematicians only.
But what about us, poor applicators of mathematical results
and theories?
We are not interested in detailed proofs and expositions
of tricky proofs techniques (we believe the mathematicians
did them right, and even if we did not believe in them,
we are not in a position to try to verify the proofs ourselves...).
We are even not interested much in theorems as such.
We are rather interested in clear and well-structured expositions
of the final results, namely definitions and properties of various
classes of objects and constructs, as well as recipes of calculating
the properties of objects, membership in a class, etc.
We are interested equally in positive results
(this can be obtained in such and such a way), negative results
(this cannot be decided for such and such a class of objects),
as well as indications of not fully investigated areas
(this and this is as yet an open question).
May we kindly ask our distinguished mathematical colleagues
to write sometimes such a textbook for us also? Please?
We will be grateful, and in exchange we will refrain from
flooding you with silly requests for explanations... ;-))
-------------------------- end of METAREMARK.
Thank you, and best regards,
-- Zenon Kulpa
From owner-reliable_computing Sun Aug 10 22:53:53 1997
Received: by interval.usl.edu id AA10346
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sun, 10 Aug 1997 13:54:07 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA10340
(5.65c/IDA-1.4.4 for ); Sun, 10 Aug 1997 13:54:02 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IMADXQA8A8E0RI9J [at] Pap [dot] UniVie.AC.AT>; Sun, 10 Aug 1997 20:53:02 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA07395; Sun, 10 Aug 1997 20:53:53 +0200
Date: Sun, 10 Aug 1997 20:53:53 +0200
From: Arnold Neumaier
Subject: Re: Linear interval systems: "combinatorial" approach
To: neum [at] homer [dot] cma.univie.ac.at, reliable_computing [at] interval [dot] usl.edu,
zkulpa [at] zmit1 [dot] ippt.gov.pl
Message-Id: <9708101853.AA07395 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
Zenon Kulpa wrote:
>>(5b) requires additional condition: D'xe >= 0.
It is not clear to me how this condition affects the argument<<
This is always satisfied for some diagonal +-1 matrix D', depending
on the actual sign pattern of xe. Because it is not known in advance,
one has to try all possible D', which raises the number of systems
from 2^n to 2^{2n}. The sign accord algorithm is more clever and
searches through at most 2^n (but often much fewer) choices of D'
until the condition D'xe >= 0 is satisfied; thats why it is faster.
>>The "combinatorial" algorithm is conceptually very simple
and easy to implement, and its complexity depends exponentially
on the actual number m of (thick) intervals in the matrix
(with m anywhere between 1 and n^2+n), whereas the RN
algorithm is much more complicated and has a complexity
exponential with 2n (and it could be that 2^m << 2^(2n)
for large systems with small number of interval coefficients(*),
or vice versa for systems with many interval coefficients).<<
Closer analysis would allow to take the best from both approaches,
by noting (as Kulpa does) that for a small number m of (thick)
intervals many of the matrices/vectors Ae and be are identical.
Thus a good implementation would need at most 2^min(m,2n) systems to
be solved, and often much fewer.
>>It seems that the question of justifying the "combinatorial"
algorithm properly still deserves some clarifying publication<<
If I remember correctly, the "combinatorial" approach is justified in
a paper by Beeck (1975 - in my list of references), or at least in one
of the papers mentioned at the top of p.230.
But note that the combinatorial approach will give false results if
used on systems containing a singular matrix, unless complemented with
some test for singularity or nonsingularity. In addition to the
material in my Chapter 6, I think that Siegfried Rump
(rump@tu-harburg.d400.de) has somewhere some results on testing
singularity or nonsingularity.
A publication spelling out implementation details and a better
exposition of Rohn's method (without proofs), and/or a combination
with the "combinatorial" algorithm would certainly be useful,
especially when presented together with numerical results on a
substantial number of problems of significant dimension.
>>For me, after browsing through Chapter 6, it was just another
theoretical exercise not worth (sorry ;-) of hard work to understand
in all necessary details and to implement, as the result will be
still an exponential-complexity algorithm but much more complicated
(so it seemed) than the simple "combinatorial" one.<<
Sorry that I didn't write more clearly. Rohn's arguments are hard
mathematics, and I think not very many people worked through all the
details. I was happy enough to have understood everything in a way
that I could present. There was also a time limit of the publisher;
with one year more time, a number of things would have become more
clear. That exponential work is unavoidable in general is a
consequence of the NP-completeness results of Poljak and Rohn (and
later authors).
>>practically all books written by mathematicians on their subjects of
study are written for another professional mathematicians only.
But what about us, poor applicators of mathematical results and
theories? We are not interested in detailed proofs and expositions of
tricky proofs techniques ... We are even not interested much in
theorems as such.<<
My book was specifically written to represent the state of the art in
techniques for proving and analysing interval algorithms. But there
are other books that concentrate much more on algorithms. Unfortunately,
computations of interval hulls for general interval linear systems
haven't made their way into such books, probably because their theory
is so intricate.
>>We are rather interested in clear and well-structured expositions
of the final results, namely definitions and properties of various
classes of objects and constructs, as well as recipes of calculating
the properties of objects, membership in a class, etc.
We are interested equally in positive results
(this can be obtained in such and such a way), negative results
(this cannot be decided for such and such a class of objects),
as well as indications of not fully investigated areas
(this and this is as yet an open question).
May we kindly ask our distinguished mathematical colleagues
to write sometimes such a textbook for us also?<<
Some years ago, George Corliss (georgec [at] boris [dot] mscs.mu.edu)
suggested a project to write a book on ``Interval Recipes'' in a
similar spirit as the well-known ``Numerical Recipes'' by Press et al..
Apparently nothing materialized, but maybe this project can be
rekindled. I certainly would help with my advice, though I am too
occupied with other things to work directly on such a book.
Arnold Neumaier
From owner-reliable_computing Fri Aug 8 13:49:52 1997
Received: by interval.usl.edu id AA10773
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 03:46:55 -0500
Received: from rztsun.rz.tu-harburg.de by interval.usl.edu with SMTP id AA10767
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 03:46:49 -0500
Message-Id: <01BCA643.78F87620@rump>
From: "Siegfried M. Rump"
To: "'reliable_computing [at] interval [dot] usl.edu'"
Subject: ####### change of mail address ######### and AW: linear systems - Help
Date: Fri, 8 Aug 1997 15:49:52 +-200
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing
Precedence: bulk
We had some problems with e-mail about 3-4 weeks ago.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++ ++++++++++++
+++++++++ My new e-mail is rump@tu-harburg.de ++++++++++++
+++++++++ ++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Since questions about linear systems with data dependencies are again in
the net, I resent my message from 4 weeks ago (which may be lost due to
our mail problems). Sorry for possible duplication.
Regards, S.M. Rump
My question concerns the solution of linear systmes of equations with interval
coefficients.
Let's consider a linear system AX=B where Aij and Bi coefficients are
functions of N interval variables. That is :
A(y1,...,yN) X = B(y1,...,yN) (1)
The first paper dealing with dependencies is
Ch. Jansson: Interval Linear Systems with Symmetric Matrices, Skew-Symmetric
Matrices and Dependencies in the Right hand Side, Computing 46, 265-274 (1991).
The idea can be extended to arbitrary linear dependencies between the matrix components
and the components of the right hand side. This is done in
S.M. Rump: Verification methods for Dense and Sparse Systems of Equations,
in "Topics in Validated Computations", ed. J. Herzberger, Elsevier Publications, 1995.
Data dependencies are treated in Chapter 4.3.
Best regards, Siegfried M. Rump
From owner-reliable_computing Mon Aug 11 12:45:04 1997
Received: by interval.usl.edu id AA11171
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 04:03:11 -0500
Received: from uivt1.uivt.cas.cz by interval.usl.edu with SMTP id AA11165
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 04:03:06 -0500
Received: from [147.231.11.66] (klicava.site.cas.cz [147.231.11.66]) by uivt1.uivt.cas.cz (8.6.12/8.6.12) with SMTP id LAA29298; Mon, 11 Aug 1997 11:01:31 +0200
Date: Mon, 11 Aug 97 10:45:04 +0200
From: "Jiri Rohn"
Message-Id: <51901.rohn [at] uivt1 [dot] uivt.cas.cz>
X-Minuet-Version: Minuet 1.0_Beta_17
X-Popmail-Charset: IBM 8-Bit
To: reliable_computing [at] interval [dot] usl.edu, zkulpa [at] zmit1 [dot] ippt.gov.pl
Subject: "combinatorial" approach
Sender: owner-reliable_computing
Precedence: bulk
The result whose validity has been recently requested by Dr. Zenon Kulpa
is true. It can be found in my paper Systems of linear interval equations,
Linear Algebra and Its Applications 126(1989), 39-78, section 2.
The shortest proof I know (different from that one given in the paper)
consists in a direct application of the Sherman-Morrison formula with
perturbation in the ij-th coefficient only. This shows that the i-th entry
of the solution is increased, or stays at the same value, if one moves
the ij-th coefficient of the matrix to one of the endpoints. Repeating this
argument, one obtains a matrix whose all coefficients are fixed at the
endpoints. The same result for the right-hand side follows immediately from
the formula $x=A^{-1}b$. Regularity assumption is needed to keep
the denominator of the fraction appearing in the Sherman-Morrison formula
nonzero (i.e., positive).
Jiri Rohn
From owner-reliable_computing Mon Aug 11 16:30:29 1997
Received: by interval.usl.edu id AA11547
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 07:48:33 -0500
Received: from uivt1.uivt.cas.cz by interval.usl.edu with SMTP id AA11541
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 07:48:28 -0500
Received: from [147.231.11.66] (klicava.site.cas.cz [147.231.11.66]) by uivt1.uivt.cas.cz (8.6.12/8.6.12) with SMTP id OAA00298 for ; Mon, 11 Aug 1997 14:47:01 +0200
Date: Mon, 11 Aug 97 14:30:29 +0200
From: "Jiri Rohn"
Message-Id: <64218.rohn [at] uivt1 [dot] uivt.cas.cz>
X-Minuet-Version: Minuet 1.0_Beta_17
X-Popmail-Charset: IBM 8-Bit
To: reliable_computing [at] interval [dot] usl.edu
Subject: letter
Sender: owner-reliable_computing
Precedence: bulk
Dear colleagues,
The recent discussion on the net with Dr. Zenon Kulpa has reminded me of
another story concerning linear interval equations. During the last years I
learned that even by far not all the specialists in linear interval
equations are aware of what I would dare to call a big breakthrough made in
1992-93, namely the existence of a simple-to-formulate polynomial-time
algorithm for computing the EXACT bounds on solution of a PRECONDITIONED
system of linear interval equations. The importance of this result can be
best understood from the fact that computing the exact bounds for a
general "unpreconditioned" system is NP-hard (SIMAX 16(1995), 415-420).
The result makes obsolete all the other methods based on preconditioning
(as e.g. the popular preconditioned interval Gaussian algorithm!). Despite
its apparent simplicity, its proof is very nontrivial (I remember in Spring
1993 it took me more than 100 working hours to understand fully Hansen's
original result and to find its proof using elementary means). I have tried
to explain the result in a one-page text describing it in the form of a
pseudo-PASCAL algorithm (which is sent in a separate LaTeX file) to make it
easily available for the interval community. I hope this will help those
colleagues who, as Dr. Kulpa says, are more interested in implementable
algorithms than in sophisticated theoretical arguments.
With best regards to all of you,
Jiri Rohn
From owner-reliable_computing Mon Aug 11 16:30:38 1997
Received: by interval.usl.edu id AA11577
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 07:48:38 -0500
Received: from uivt1.uivt.cas.cz by interval.usl.edu with SMTP id AA11558
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 07:48:33 -0500
Received: from [147.231.11.66] (klicava.site.cas.cz [147.231.11.66]) by uivt1.uivt.cas.cz (8.6.12/8.6.12) with SMTP id OAA00301 for ; Mon, 11 Aug 1997 14:47:05 +0200
Date: Mon, 11 Aug 97 14:30:38 +0200
From: "Jiri Rohn"
Message-Id: <64221.rohn [at] uivt1 [dot] uivt.cas.cz>
X-Minuet-Version: Minuet 1.0_Beta_17
X-Popmail-Charset: IBM 8-Bit
To: reliable_computing [at] interval [dot] usl.edu
Subject: algorithm
Sender: owner-reliable_computing
Precedence: bulk
\documentstyle[12pt]{article}
\pagestyle{empty}
\textwidth 154mm
\textheight 220mm
\oddsidemargin 4mm
\evensidemargin 4mm
\topmargin -8mm
\parindent2.5ex
\pagenumbering{arabic}
\newcommand{\ai}{A^I}
\newcommand{\ac}{A_c}
\newcommand{\aci}{A_c^{-1}}
\newcommand{\acd}{[A_c-\Delta,A_c+\Delta]}
\newcommand{\bi}{b^I}
\newcommand{\bcd}{[b_c-\delta,b_c+\delta]}
\newcommand{\ux}{\underline x}
\newcommand{\ox}{\overline x}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\h}{\hspace*{3ex}}
\begin{document}
\noindent Given a system of linear interval equations
\be \ai x=\bi \label{1} \ee
with $\ai=\acd$ square and $\bi=\bcd$, the following algorithm computes
the {\bf optimal} enclosure $[\ux,\ox]$ of the solution set of the
preconditioned system
\be (\aci\odot\ai) x=\aci\odot\bi \label{2} \ee
(multiplication in interval arithmetic), which is thereby also an enclosure
of the solution set of (\ref{1}). The algorithm is polynomial-time
(requires two matrix inversions), fails if and only if the preconditioned
matrix is singular, and can be {\bf strongly recommended} for computing
enclosures of solutions of (\ref{1}). The original idea of the algorithm
goes back to Hansen \cite{Ha} and Bliek \cite{Bliek}, the present form is based
on results in Rohn \cite{Ro69} where it can be also seen that the proof
of this result is nontrivial ($I$ is the unit matrix and absolute
values are taken componentwise):\\
%\smallskip
\\
$G:=I-|\aci|\Delta$;\\
{\bf if} $G$ is singular or $G^{-1}\not\geq 0$\\
{\bf then} terminate: preconditioned matrix $\aci\odot\ai$ is singular\\
{\bf else}\\
\h $M:=G^{-1}$;\\
\h $x^c:=\aci b_c$;\\
\h $x^{\ast}:=M(|x^c|+|\aci|\delta)$;\\
\h {\bf for} $i:=1$ {\bf to} $n$ {\bf do}\\
\h\h ${\ux}_i:=-x^{\ast}_i+M_{ii}(x^c_i+|x^c_i|)$;\\
\h\h {\bf if} ${\ux}_i>0$ {\bf then} ${\ux}_i:={\ux}_i/(2M_{ii}-1)$;\\
\h\h ${\ox}_i:=x^{\ast}_i+M_{ii}(x^c_i-|x^c_i|)$;\\
\h\h {\bf if} ${\ox}_i<0$ {\bf then} ${\ox}_i:={\ox}_i/(2M_{ii}-1)$\\
\{then $[\ux,\ox]$ is the optimal enclosure for (\ref{2}) and an
enclosure for (\ref{1})\}.
\begin{thebibliography}{1}
\bibitem{Ha}
E.~R. Hansen.
\newblock Bounding the solution of interval linear equations.
\newblock {\em SIAM Journal on Numerical Analysis}, 29:1493--1503, 1992.
\bibitem{Bliek}
C.~Bliek.
\newblock {\em Computer Methods for Design Automation}.
\newblock PhD thesis, Massachusetts Institute of Technology, Cambridge, MA,
July 1992.
\bibitem{Ro69}
J.~Rohn.
\newblock Cheap and tight bounds: {T}he recent result by {E}.~{H}ansen can be
made more efficient.
\newblock {\em Interval Computations}, 4:13--21, 1993.
\end{thebibliography}
\end{document}
From owner-reliable_computing Mon Aug 11 17:10:32 1997
Received: by interval.usl.edu id AA12171
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 08:11:11 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA12164
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 08:11:05 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id PAA07652; Mon, 11 Aug 1997 15:10:32 +0200 (MET DST)
Date: Mon, 11 Aug 1997 15:10:32 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708111310.PAA07652 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu, rohn [at] uivt [dot] cas.cz
Subject: Re: letter
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: "Jiri Rohn"
>
> The recent discussion on the net with Dr. Zenon Kulpa has reminded me of
> another story concerning linear interval equations. During the last years
> I learned that even by far not all the specialists in linear interval
> equations are aware of what I would dare to call a big breakthrough made
> in 1992-93, namely the existence of a simple-to-formulate polynomial-time
> algorithm for computing the EXACT bounds on solution of a PRECONDITIONED
> system of linear interval equations. The importance of this result can be
> best understood from the fact that computing the exact bounds for a
> general "unpreconditioned" system is NP-hard (SIMAX 16(1995), 415-420).
>
That sounds too good to be true ;-)
Namely, I have some doubts:
- if it is possible to find appropriate preconditioning
for every initial matrix, then either:
-- finding this preconditioning must be NP-hard, or
-- SIMAX 16(1995) result is false...
- if appropriate preconditioning cannot be found for some
initial matrices, the usefulness of the algorithm is limited,
unless the class of "nonpreconditionable" matrices
is characterized and found not very significant for practical problems...
Best regards,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 11 19:04:18 1997
Received: by interval.usl.edu id AA12541
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 10:05:14 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA12535
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 10:04:58 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id RAA07843; Mon, 11 Aug 1997 17:04:18 +0200 (MET DST)
Date: Mon, 11 Aug 1997 17:04:18 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708111504.RAA07843 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu, neum [at] cma [dot] univie.ac.at
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Arnold Neumaier
>
> >>From Zenon Kulpa:
> >>(5b) requires additional condition: D'xe >= 0.
> It is not clear to me how this condition affects the argument<<
>
> This is always satisfied for some diagonal +-1 matrix D', depending
> on the actual sign pattern of xe. Because it is not known in advance,
> one has to try all possible D', which raises the number of systems
> from 2^n to 2^{2n}. The sign accord algorithm is more clever and
> searches through at most 2^n (but often much fewer) choices of D'
> until the condition D'xe >= 0 is satisfied; thats why it is faster.
>
Does it follow from that, that there is at most 2^n extremal points
in the solution set? The bound 2^n cannot be lowered, as examples
with 2^n extremal points abound.
> >>The "combinatorial" algorithm is conceptually very simple
> and easy to implement, and its complexity depends exponentially
> on the actual number m of (thick) intervals in the matrix
> (with m anywhere between 1 and n^2+n), whereas the RN
> algorithm is much more complicated and has a complexity
> exponential with 2n (and it could be that 2^m << 2^(2n)
> for large systems with small number of interval coefficients(*),
> or vice versa for systems with many interval coefficients).<<
>
> Closer analysis would allow to take the best from both approaches,
> by noting (as Kulpa does) that for a small number m of (thick)
> intervals many of the matrices/vectors Ae and be are identical.
> Thus a good implementation would need at most 2^min(m,2n) systems to
> be solved, and often much fewer.
>
> >>It seems that the question of justifying the "combinatorial"
> algorithm properly still deserves some clarifying publication<<
>
> If I remember correctly, the "combinatorial" approach is justified in
> a paper by Beeck (1975 - in my list of references), or at least in one
> of the papers mentioned at the top of p.230.
>
Thank you, I will try to find them out.
> But note that the combinatorial approach will give false results if
> used on systems containing a singular matrix, unless complemented with
> some test for singularity or nonsingularity. In addition to the
> material in my Chapter 6, I think that Siegfried Rump
> (rump@tu-harburg.d400.de) has somewhere some results on testing
> singularity or nonsingularity.
>
The "combinatorial" approach offers a simple "singularity testing"
procedure, albeit exponential in min(m,2n) and inconclusive
when the matrix happens to be regular, but possibly still useful
in practice:
1. Use the "combinatorial"/RN algorithm to find the exact
enclosure of the solution set. If one of the 2^min(m,2n) matrices
occuring during its run is singular, the original system is singular;
otherwise go to 2.
2. Pick randomly a real matrix belonging to the interior of the
original interval matrix in the system:
-- if it is singular or if the solution using this matrix
falls OUTSIDE the bounds computed at Step 1,
the original system is singular, otherwise:
-- if your patience or computer time available is not
exhausted, go to 2 again, else stop (result inconclusive).
Of course, with better (e.g. polynomial, if it exists) algorithm
for calculating the EXACT enclosure, it can be substituted
in Step 1 for the "cobinatorial" one, with benefit.
> A publication spelling out implementation details and a better
> exposition of Rohn's method (without proofs), and/or a combination
> with the "combinatorial" algorithm would certainly be useful,
> especially when presented together with numerical results on a
> substantial number of problems of significant dimension.
>
Possibly a good problem for a M.Sc. thesis too?
> >>For me, after browsing through Chapter 6, it was just another
> theoretical exercise not worth (sorry ;-) of hard work to understand
> in all necessary details and to implement, as the result will be
> still an exponential-complexity algorithm but much more complicated
> (so it seemed) than the simple "combinatorial" one.<<
>
> Sorry that I didn't write more clearly. Rohn's arguments are hard
> mathematics, and I think not very many people worked through all the
> details. I was happy enough to have understood everything in a way
> that I could present. There was also a time limit of the publisher;
> with one year more time, a number of things would have become more
> clear.
>
It seems mathematicians have also sometimes troubles with works
of their colleagues. It is encouraging for us, nonprofessionalists
in this difficult trade ;-)
And it once again reminds me of the basic problem of all creators
(e.g., book-writers): if only the said creator have had more time,
the result would be certainly better, but, on the other hand,
if the creator really have had all that time, the creation may
never materialize... Which may be used as a sketch for the proof
that no creation can be perfect. ;-)
> That exponential work is unavoidable in general is a
> consequence of the NP-completeness results of Poljak and Rohn (and
> later authors).
>
See my reply to Rohn's letter about a polynomial algorithm...
> >>practically all books written by mathematicians on their subjects of
> study are written for another professional mathematicians only.
> But what about us, poor applicators of mathematical results and
> theories? We are not interested in detailed proofs and expositions of
> tricky proofs techniques ... We are even not interested much in
> theorems as such.<<
>
> My book was specifically written to represent the state of the art in
> techniques for proving and analysing interval algorithms. But there
> are other books that concentrate much more on algorithms. Unfortunately,
> computations of interval hulls for general interval linear systems
> haven't made their way into such books, probably because their theory
> is so intricate.
>
> >>We are rather interested in clear and well-structured expositions
> of the final results, namely definitions and properties of various
> classes of objects and constructs, as well as recipes of calculating
> the properties of objects, membership in a class, etc.
> We are interested equally in positive results
> (this can be obtained in such and such a way), negative results
> (this cannot be decided for such and such a class of objects),
> as well as indications of not fully investigated areas
> (this and this is as yet an open question).
> May we kindly ask our distinguished mathematical colleagues
> to write sometimes such a textbook for us also?<<
>
> Some years ago, George Corliss (georgec [at] boris [dot] mscs.mu.edu)
> suggested a project to write a book on ``Interval Recipes'' in a
> similar spirit as the well-known ``Numerical Recipes'' by Press et al..
> Apparently nothing materialized, but maybe this project can be
> rekindled. I certainly would help with my advice, though I am too
> occupied with other things to work directly on such a book.
>
What I have in mind was not necessarily a book of ready-to-run
algorithmic recipes.
It is impossible to cover all cases that may arise in practice
with such a set of recipes, and without enough knowledge about
the "technology" of the ingredients and their properties,
underlying the recipes, it is hard, if at all possible, to adapt
the recipes to particular applications, or justify their validity
for the given circumstances.
I am not against algorithms, or even recipes, of course,
but I would rather like to see the book covering also
the underlying theory, though exposed and organized differently
than it is done usually in books written for fellow mathematicians.
With many thanks,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 11 03:16:27 1997
Received: by interval.usl.edu id AA12817
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 10:16:32 -0500
Received: from csc-sun.math.utah.edu by interval.usl.edu with SMTP id AA12811
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 10:16:30 -0500
Received: from plot79.math.utah.edu (beebe [at] plot79 [dot] math.utah.edu [128.110.198.3])
by csc-sun.math.utah.edu (8.8.5/8.8.5) with ESMTP id JAA11190;
Mon, 11 Aug 1997 09:16:27 -0600 (MDT)
From: "Nelson H. F. Beebe"
Received: (from beebe@localhost)
by plot79.math.utah.edu (8.8.5/8.8.5) id JAA29161;
Mon, 11 Aug 1997 09:16:27 -0600 (MDT)
Date: Mon, 11 Aug 1997 09:16:27 -0600 (MDT)
To: reliable_computing [at] interval [dot] usl.edu
Cc: beebe [at] math [dot] utah.edu
X-Us-Mail: "Center for Scientific Computing, University of Utah, Salt Lake
City, UT 84112, USA"
X-Telephone: +1 801 581 5254
X-Fax: +1 801 581 4148
X-Url: http://www.math.utah.edu/~beebe
Subject: Re: Beeck reference
Message-Id:
Sender: owner-reliable_computing
Precedence: bulk
Correspondence on this list earlier today said:
> If I remember correctly, the "combinatorial" approach is justified in
> a paper by Beeck (1975 - in my list of references), or at least in one
> of the papers mentioned at the top of p.230.
Perhaps this is the paper referred to:
URL=ftp://ftp.math.utah.edu/pub/tex/bib/intarith.bib Line=11546
@InProceedings{Beeck:1975:PHI,
author = "H. Beeck",
editor = "K. Nickel",
booktitle = "Interval Mathematics",
title = "{Zur Problematik Der H{\"u}llenbestimmung Von
Intervallgleichungssystemen}",
volume = "29",
publisher = "Springer Verlag",
pages = "150--159",
year = "1975",
bibdate = "Fri Jan 12 11:37:56 1996",
series = "Lecture Notes In Computer Science",
acknowledgement = ack-jr,
}
========================================================================
Nelson H. F. Beebe Tel: +1 801 581 5254
Center for Scientific Computing FAX: +1 801 581 4148
Department of Mathematics, 105 JWB Internet: beebe [at] math [dot] utah.edu
University of Utah URL: http://www.math.utah.edu/~beebe
Salt Lake City, UT 84112, USA
========================================================================
From owner-reliable_computing Mon Aug 11 03:33:52 1997
Received: by interval.usl.edu id AA13165
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 10:33:58 -0500
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA13159
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 10:33:55 -0500
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA27851; Mon, 11 Aug 97 09:33:52 MDT
Date: Mon, 11 Aug 97 09:33:52 MDT
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9708111533.AA27851 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Re: letter
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From owner-reliable_computing [at] interval [dot] usl.edu Mon Aug 11 07:14:07 1997
> Date: Mon, 11 Aug 1997 15:10:32 +0200 (MET DST)
> From: Zenon Kulpa
> > best understood from the fact that computing the exact bounds for a
> > general "unpreconditioned" system is NP-hard (SIMAX 16(1995), 415-420).
> >
> That sounds too good to be true ;-)
> Namely, I have some doubts:
> - if it is possible to find appropriate preconditioning
> for every initial matrix, then either:
> -- finding this preconditioning must be NP-hard, or
This is exactly the conclusion that we can make from the two results:
that in general, finding the exact enclosures is NP-hard and that
solving pre-conditioned systems is polynomial-time.
> -- SIMAX 16(1995) result is false...
There are several proofs of this NP-hardness result by now, and some of
them are pretty transparent and easy to check (papers in Reliable
Computing etc.), so I do not think that there is any reason to doubt
it.
> - if appropriate preconditioning cannot be found for some
> initial matrices, the usefulness of the algorithm is limited,
NP-hard means, crudely speaking, that every algorithm for solving a
problem requires, in some cases, exponential time. In this sense, of
course, this algorithm does not solve ALL non-preconditioned problems
in polynomial time, but this is not the drawback of an algorithm, but
the consequence of NP-hardness.
NP-hard does not necessarily mean that there are matrices for whcih
EVERY algorithm requires exponential time: it could as well be that for
every reasonable sequence of matrices, there is a polynpmial-time
algorithm, but NP-hardness does mean that whatever algorithm we use,
for some hard matrices we will get exponential time. However, which
matrices are hard may depend on an algorithm (as always): matrices that
are hard for one algorithm may be easily solvable by some other
algorithm.
> unless the class of "nonpreconditionable" matrices
> is characterized and found not very significant for practical problems...
See comment above.
Yours
Vladik
From owner-reliable_computing Mon Aug 11 19:48:41 1997
Received: by interval.usl.edu id AA13474
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 10:49:09 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA13468
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 10:49:04 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IMBLRGKOLSE0ROHF [at] Pap [dot] UniVie.AC.AT>; Mon, 11 Aug 1997 17:47:50 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA08331; Mon, 11 Aug 1997 17:48:41 +0200
Date: Mon, 11 Aug 1997 17:48:41 +0200
From: Arnold Neumaier
Subject: Re: Linear interval systems: "combinatorial" approach
To: neum [at] homer [dot] cma.univie.ac.at, reliable_computing [at] interval [dot] usl.edu,
zkulpa [at] zmit1 [dot] ippt.gov.pl
Message-Id: <9708111548.AA08331 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
>>
The "combinatorial" approach offers a simple "singularity testing"
procedure, albeit exponential in min(m,2n) and inconclusive
when the matrix happens to be regular, but possibly still useful
in practice:
1. Use the "combinatorial"/RN algorithm to find the exact
enclosure of the solution set. If one of the 2^min(m,2n) matrices
occuring during its run is singular, the original system is singular;
otherwise go to 2.
2. Pick randomly a real matrix belonging to the interior of the
original interval matrix in the system:
-- if it is singular or if the solution using this matrix
falls OUTSIDE the bounds computed at Step 1,
the original system is singular, otherwise:
-- if your patience or computer time available is not
exhausted, go to 2 again, else stop (result inconclusive).
<<
This is a very poor test, and will not identify most singular interval
matrices. And you'll never know whether the enclosure computed in step 1
is valid...
>>
> A publication spelling out implementation details and a better
> exposition of Rohn's method (without proofs), and/or a combination
> with the "combinatorial" algorithm would certainly be useful,
> especially when presented together with numerical results on a
> substantial number of problems of significant dimension.
>
Possibly a good problem for a M.Sc. thesis too?
<<
Yes.
>>
I am not against algorithms, or even recipes, of course,
but I would rather like to see the book covering also
the underlying theory, though exposed and organized differently
than it is done usually in books written for fellow mathematicians.
<<
This is what the ``Numerical Recipes'' by Press et al. do, and what good
``Interval Recipes'' should do as well.
Arnold Neumaier
From owner-reliable_computing Mon Aug 11 20:04:14 1997
Received: by interval.usl.edu id AA13773
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 11:04:58 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA13767
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 11:04:44 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IMBMBTPYOGE0RQCX [at] Pap [dot] UniVie.AC.AT>; Mon, 11 Aug 1997 18:03:29 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA31864; Mon, 11 Aug 1997 18:04:14 +0200
Date: Mon, 11 Aug 1997 18:04:14 +0200
From: Arnold Neumaier
Subject: Re: letter
To: reliable_computing [at] interval [dot] usl.edu, vladik [at] cs [dot] utep.edu
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Message-Id: <9708111604.AA31864 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
>>
> > best understood from the fact that computing the exact bounds for a
> > general "unpreconditioned" system is NP-hard (SIMAX 16(1995), 415-420).
> >
> That sounds too good to be true ;-)
> Namely, I have some doubts:
> - if it is possible to find appropriate preconditioning
> for every initial matrix, then either:
> -- finding this preconditioning must be NP-hard, or
This is exactly the conclusion that we can make from the two results:
that in general, finding the exact enclosures is NP-hard and that
solving pre-conditioned systems is polynomial-time.
<<
No; the dilemma is solved by noting that the hull of the preconditioned
system is usually an overestimate of the hull of the original system.
Thus the two results apply to different problems. What the Hansen-Rohn
result says is that interval systems whose coefficient matrix has the
identity as midpoint can be optimally enclosed in O(n^3) operations.
The recent paper by Ning and Kearfott, quoted below, extends this
slightly to interval systems where all off-diagonal entries have
midpoint zero.
Arnold Neumaier
-------
S. Ning, R. B. Kearfott
A Comparison of some Methods for Solving Linear Interval
Equations
SIAM Journal on Numerical Analysis Volume 34, Issue 4, August 1997
(Pages 1289 - 1305)
http://epubs.siam.org/sam-bin/dbq/toc/SINUM/34/4
From owner-reliable_computing Mon Aug 11 20:52:28 1997
Received: by interval.usl.edu id AA14104
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 11:53:10 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA14098
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 11:53:04 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id SAA07939; Mon, 11 Aug 1997 18:52:28 +0200 (MET DST)
Date: Mon, 11 Aug 1997 18:52:28 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708111652.SAA07939 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu, neum [at] cma [dot] univie.ac.at
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Arnold Neumaier
>
> >>
> The "combinatorial" approach offers a simple "singularity testing"
> procedure, albeit exponential in min(m,2n) and inconclusive
> when the matrix happens to be regular, but possibly still useful
> in practice:
> 1. Use the "combinatorial"/RN algorithm to find the exact
> enclosure of the solution set. If one of the 2^min(m,2n) matrices
> occuring during its run is singular, the original system is singular;
> otherwise go to 2.
> 2. Pick randomly a real matrix belonging to the interior of the
> original interval matrix in the system:
> -- if it is singular or if the solution using this matrix
> falls OUTSIDE the bounds computed at Step 1,
> the original system is singular, otherwise:
> -- if your patience or computer time available is not
> exhausted, go to 2 again, else stop (result inconclusive).
> <<
> This is a very poor test, and will not identify most singular interval
> matrices. And you'll never know whether the enclosure computed in step 1
> is valid...
>
Yes, as I have said, the algorithm is inconclusive for regular matrices,
and of course it does not quarantee finding in reasonable
time that the matrix is singular even when it is.
Thus, its usefulness is exactly the same as the usefulness
of testing computer programs: you may find bugs in this way
(if you are lucky enough), but you cannot assure correctness
of the program.
What does not stop program testing of being a widely used technique,
and explains the buggy nature of most of the software we use... ;-)
> I am not against algorithms, or even recipes, of course,
> but I would rather like to see the book covering also
> the underlying theory, though exposed and organized differently
> than it is done usually in books written for fellow mathematicians.
> <<
> This is what the ``Numerical Recipes'' by Press et al. do,
> and what good ``Interval Recipes'' should do as well.
>
Good to hear that.
So I am waiting for the "Interval recipes"!
I may offer my service as a critic, complaining that
this or that part is still too intricate and hard to understand...
Best regards,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 11 21:05:22 1997
Received: by interval.usl.edu id AA14387
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 12:06:00 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA14381
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 12:05:56 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id TAA07952; Mon, 11 Aug 1997 19:05:22 +0200 (MET DST)
Date: Mon, 11 Aug 1997 19:05:22 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708111705.TAA07952 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Re: letter
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
> From: Arnold Neumaier
>
> > > [Rohn: ]
> > > best understood from the fact that computing the exact bounds for a
> > > general "unpreconditioned" system is NP-hard (SIMAX 16(1995), 415-420).
> > >
> > [Zenon:]
> > That sounds too good to be true ;-)
> > Namely, I have some doubts:
> > - if it is possible to find appropriate preconditioning
> > for every initial matrix, then either:
> > -- finding this preconditioning must be NP-hard, or
>
> [Vladik:]
> This is exactly the conclusion that we can make from the two results:
> that in general, finding the exact enclosures is NP-hard and that
> solving pre-conditioned systems is polynomial-time.
> <<
> No; the dilemma is solved by noting that the hull of the preconditioned
> system is usually an overestimate of the hull of the original system.
> Thus the two results apply to different problems.
>
After reading the description of the Rohn's algorithm
in his another letter, it seems you are right.
Let me quote from Rohn:
"... algorithm computes the _optimal_ enclosure of the solution set
of the preconditioned system [...] which is thereby also an enclosure
of the solution set of (1)". Note the word "optimal" has not been
used in reference to the solution set of the original problem...
Another important remark in that description:
"The algorithm [...] fails if and only if the _preconditioned_ matrix
is singular...". Hence for some systems [namely, those for which
(mid A)^(-1) . A is singular] it does not work.
As far as I understand, this can happen also for some
regular matrices A?
> What the Hansen-Rohn
> result says is that interval systems whose coefficient matrix has the
> identity as midpoint can be optimally enclosed in O(n^3) operations.
> The recent paper by Ning and Kearfott, quoted below, extends this
> slightly to interval systems where all off-diagonal entries have
> midpoint zero.
>
Does this result allow for modifications of the Rohn's algorithm
so that it can solve a wider class of systems?
Best regards,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 11 21:55:48 1997
Received: by interval.usl.edu id AA14781
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 12:56:31 -0500
Received: from Pap.UniVie.AC.AT (apap4.pap.univie.ac.at) by interval.usl.edu with SMTP id AA14775
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 12:56:27 -0500
Received: from homer.cma.univie.ac.at by Pap.UniVie.AC.AT (PMDF V5.0-4 #10670)
id <01IMBQ806X5CE0RQO0 [at] Pap [dot] UniVie.AC.AT>; Mon, 11 Aug 1997 19:54:55 +0100 (MET)
Received: by homer.cma.univie.ac.at (5.65v3.2/1.1.10.5/19Mar97-1148AM)
id AA09078; Mon, 11 Aug 1997 19:55:48 +0200
Date: Mon, 11 Aug 1997 19:55:48 +0200
From: Arnold Neumaier
Subject: Re: letter
To: reliable_computing [at] interval [dot] usl.edu, zkulpa [at] zmit1 [dot] ippt.gov.pl
Message-Id: <9708111755.AA09078 [at] homer [dot] cma.univie.ac.at>
Content-Transfer-Encoding: 7BIT
Sender: owner-reliable_computing
Precedence: bulk
>>
"The algorithm [...] fails if and only if the _preconditioned_ matrix
is singular...". Hence for some systems [namely, those for which
(mid A)^(-1) . A is singular] it does not work.
As far as I understand, this can happen also for some
regular matrices A?
<<
Yes. It happens precisely when the matrix is not strongly regular.
It is easy to construct already 2x2 counterexamples.
>>
> The recent paper by Ning and Kearfott, quoted below, extends this
> slightly to interval systems where all off-diagonal entries have
> midpoint zero.
>
Does this result allow for modifications of the Rohn's algorithm
so that it can solve a wider class of systems?
<<
Theorem 2.2 in Ning and Kearfott applies for all H-matrices, but
gives the hull probably only in the case mentioned. In any case,
it gives an enclosure for the hull.
Arnold Neumaier
From owner-reliable_computing Mon Aug 11 23:38:29 1997
Received: by interval.usl.edu id AA15143
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 11 Aug 1997 14:57:41 -0500
Received: from uivt1.uivt.cas.cz by interval.usl.edu with SMTP id AA15137
(5.65c/IDA-1.4.4 for ); Mon, 11 Aug 1997 14:57:38 -0500
Received: from [147.231.11.66] (klicava.site.cas.cz [147.231.11.66]) by uivt1.uivt.cas.cz (8.6.12/8.6.12) with SMTP id VAA01908; Mon, 11 Aug 1997 21:55:29 +0200
Date: Mon, 11 Aug 97 21:38:29 +0200
From: "Jiri Rohn"
Message-Id: <87591.rohn [at] uivt1 [dot] uivt.cas.cz>
X-Minuet-Version: Minuet 1.0_Beta_17
X-Popmail-Charset: IBM 8-Bit
To: zkulpa [at] zmit1 [dot] ippt.gov.pl, reliable_computing [at] interval [dot] usl.edu
Subject: Re: letter
Sender: owner-reliable_computing
Precedence: bulk
>Namely, I have some doubts:
>- if it is possible to find appropriate preconditioning
> for every initial matrix, then either:
> -- finding this preconditioning must be NP-hard, or
> -- SIMAX 16(1995) result is false...
>- if appropriate preconditioning cannot be found for some
> initial matrices, the usefulness of the algorithm is limited,
> unless the class of "nonpreconditionable" matrices
> is characterized and found not very significant for practical problems...
Although Arnold Neumaier and Vladik Kreinovich have already responded to
this, I feel I must also add my explanation since I was probably too
brief in my previous text which might have caused this misunderstanding:
1. no "appropriate preconditioning" is being looked for; by definition,
preconditioning by the midpoint inverse is meant, see equation (2) in
the text on the algorithm;
2. as is well known, preconditioning usually enlarges the solution set X
to some set X'; the results in question say that computing the exact
hull of X' can be done by the polynomial-time algorithm described,
whereas computing the exact hull of X is NP-hard;
3. "usefullness of the [polynomial-time] algorithm": it works as soon as
the preconditioned interval matrix is regular which is the case if
and only if the original interval matrix is strongly regular [see
Neumaier's book for explanation].
Jiri Rohn
From owner-reliable_computing Mon Aug 18 20:09:18 1997
Received: by interval.usl.edu id AA18417
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 18 Aug 1997 11:10:13 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA18411
(5.65c/IDA-1.4.4 for ); Mon, 18 Aug 1997 11:10:05 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id SAA15932; Mon, 18 Aug 1997 18:09:18 +0200 (MET DST)
Date: Mon, 18 Aug 1997 18:09:18 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708181609.SAA15932 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Re: Linear interval systems: "combinatorial" approach
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
I would like to thank all people on this list that answered
my letters on this subject and provided lots of valuable
information, explanation and advice.
As a sort of recapitulation,
I would like to add the following remarks.
1) In reply to Arnold Neumaier:
> Date: Sun, 10 Aug 1997 20:53:53 +0200
> From: Arnold Neumaier
>
> If I remember correctly, the "combinatorial" approach is justified in
> a paper by Beeck (1975 - in my list of references), or at least in one
> of the papers mentioned at the top of p.230.
>
I have found all publications mentioned "at the top of p.230".
Of these, only the paper
D.J. Hartfiel, Concerning the solution set...,
Numer. Math. 35, 355-369, 1980
contains results closely related to the "combinatorial" algorithm.
Namely, Theorem 1 there states that Convex S = Convex{x | x = E^(-1).e},
where S is the set of all solutions of Ax=b ( S = Sigma(A,b), using
the notation of Neumaier) and E and e are all real matrices
(resp. vectors) obtained as all combinations of endpoints
of the matrix A (resp. vector b). With a single reasoning step
we can get Hull{E^(-1).e} = Hull S, which is the symbolic formulation
of the "combinatorial" algorithm.
The paper then proceeds toward formulation of the algoritm for finding
all vertices of S (also those that are not extremal).
However, the algorithm as published seems to be incomplete -
some last step(s) is(are) obviously missing.
Of other literature mentioned there, H. Beeck paper
("Zur Problematik...", In: Interval Mathematics, LNCS 29,
Springer, Berlin 1975, 150-159) gives a simple iterative algorithm
using only some combinations of endpoints.
It requires the computation of at most 2n real systems of equations
but works only for "inverse nonnegative" matrices.
D. Braess paper
("Die Berechnung...", Arch.Rat. Mech. Anal., 19, 1965, 74-80)
is seemingly not relevant to the subject (at last,
I do not see the relation).
Two papers by E. Hansen (1969) discuss essentially the algorithm
described in Chapter 17 of Alefeld and Herzberger 1983 book
as "the procedure of Kuperman and Hansen". It uses endpoints,
but only for some coefficients (for which partial derivatives of
solutions are of the same sign for all A~ in A), leading to
the reformulation of the original system Ax=b into 2n equations
(two INTERVAL systems, but simpler, with smaller number
of interval coefficients).
Interesting that the description of just this procedure
in A&H book originated my doubts as to the validity
of "combinatorial" algorithm...
Concerning I.B. Kuperman's book (Van Nostrand 1971), I have had
not enough time to study it in necessary details to asses
its relevance to the problem - it is written from another
point of view and using very different notation
and conceptualization than all of the interval literature
I have read so far.
2) In reply to Jiri Rohn:
> Date: Mon, 11 Aug 97 10:45:04 +0200
> From: "Jiri Rohn"
>
> The result whose validity has been recently requested by Dr. Zenon Kulpa
> is true. It can be found in my paper Systems of linear interval equations,
> Linear Algebra and Its Applications 126(1989), 39-78, section 2.
>
> The shortest proof I know (different from that one given in the paper)
> consists in a direct application of the Sherman-Morrison formula with
> perturbation in the ij-th coefficient only. This shows that the i-th entry
> of the solution is increased, or stays at the same value, if one moves
> the ij-th coefficient of the matrix to one of the endpoints. Repeating this
> argument, one obtains a matrix whose all coefficients are fixed at the
> endpoints. The same result for the right-hand side follows immediately from
> the formula $x=A^{-1}b$. Regularity assumption is needed to keep
> the denominator of the fraction appearing in the Sherman-Morrison formula
> nonzero (i.e., positive).
>
I would like to thank Prof. Rohn for sending me a copy of this paper.
I must admit that the original Rohn's formulation is,
for me at last, more clear and understandbale that its rendering
in Chapter 6 of Neumaier's book.
However, the result reported here is distanced from the
"combinatorial" algorithm by more reasoning steps than
the Theorem 1 in Hartfiel paper mentioned above.
Namely, from the very beginning Rohn considers only
a subset of all endpoint combinations (he uses only
2^(2n) combinations instead than 2^m, where m = n^2 + n
in the general case).
3) In reply to Eldon Hansen:
> Date: Fri, 8 Aug 1997 13:15:36 -0700
> From: Bill.Walster [at] eng [dot] sun.com (William Walster)
>
> Here is a proof I received from Eldon Hansen.
>
[...]
> Bill:The "combinatorial" method is valid if the matrix is regular. I'll
> outline a proof:
>
[...]
> The difficulty with the singular case is that the combinatorial
> solution can give the exterior of the solution. Consider Kreinovich's
> scalar example [-1,1]x=[0,1]. For x>=0, we have [-x,x]=[0,1]. For the
> intervals to overlap, we need -x<=1 or x>=0 so at least x>=0. For x<=0,
> we have [x, -x]=[0,1] so x<=1 or -x>=0. The combined result is the
> entire real line. The candidate combinatorial solutions are -0 and +0.
> The solution is the the exterior of the these points instead of the
> interior.
>
Correction: the combinatorial solutions in this case are {-1, 0, 1},
hence the combinatorial estimate would be [-1, 1], not [0, 0].
The sketch of a proof given by Hansen (omitted here) seems to be
possible to reformulate as an algorithm for finding all vertices
of the solution set Sigma(A,b), simpler and much more clear
than that given in the Hartfiel paper mentioned above.
Is such an algorithm published somewhere?
With many thanks,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 18 20:40:35 1997
Received: by interval.usl.edu id AA18559
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 18 Aug 1997 11:41:21 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA18553
(5.65c/IDA-1.4.4 for ); Mon, 18 Aug 1997 11:41:15 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id SAA15984; Mon, 18 Aug 1997 18:40:35 +0200 (MET DST)
Date: Mon, 18 Aug 1997 18:40:35 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708181640.SAA15984 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Benchmark problems
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
Is there available somewhere a set of benchmark
interval linear systems of equations
(both regular and singular)?
If so, what about putting it on the interval WWW site?
If not, why not compile such a set, using this list?
Regards,
-- Zenon Kulpa
From owner-reliable_computing Mon Aug 18 20:51:02 1997
Received: by interval.usl.edu id AA18614
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 18 Aug 1997 11:51:47 -0500
Received: from zmit1.ippt.gov.pl by interval.usl.edu with SMTP id AA18608
(5.65c/IDA-1.4.4 for ); Mon, 18 Aug 1997 11:51:42 -0500
Received: (from zkulpa@localhost) by zmit1.ippt.gov.pl (8.8.5/8.7.3-zmit) id SAA15991; Mon, 18 Aug 1997 18:51:02 +0200 (MET DST)
Date: Mon, 18 Aug 1997 18:51:02 +0200 (MET DST)
From: Zenon Kulpa
Message-Id: <199708181651.SAA15991 [at] zmit1 [dot] ippt.gov.pl>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Singular interval systems
Cc: zkulpa [at] zmit1 [dot] ippt.gov.pl
Sender: owner-reliable_computing
Precedence: bulk
In practical applications of interval arithmetic,
there can be problems where putting given interval values
for some parameters results in some variables becoming
unrestricted (i.e., ranging from -Inf to +Inf).
With linear interval systems of equations, this means
that the system's matrix is singular.
However, also in this case some variables can be bounded,
hence the solution set Sigma(A,b) is unbounded only along
some of the dimensions xi (for examples see the book by I.B. Kuperman,
Approximate Linear Algebraic Equations, Van Nostrand, London 1971).
It amounts to finding bounds (or estimates of ones) for
singular systems of interval equations too.
The possibility may be very useful for certain practical
applications.
Are there some works in this area?
Regards,
-- Zenon Kulpa
From owner-reliable_computing Tue Aug 19 07:42:15 1997
Received: by interval.usl.edu id AA19943
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 19 Aug 1997 14:42:28 -0500
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA19937
(5.65c/IDA-1.4.4 for ); Tue, 19 Aug 1997 14:42:21 -0500
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA04876; Tue, 19 Aug 97 13:42:15 MDT
Date: Tue, 19 Aug 97 13:42:15 MDT
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9708191942.AA04876 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Solopchenko is 60
Sender: owner-reliable_computing
Precedence: bulk
Solopchenko is 60
On September 27, 1997, Gennadii N. Solopchenko will turn 60.
Professor Solopchenko was one of the pioneers of using interval
computations and similar techniques for estimating errors
of indirect measurements. In the 1980s, he successfully served as
a Principal Investigator (P.I.) or a co-P.I.
on several related research projects
supported by the Soviet Science Foundation and by the Soviet
National Bureau of Standards, such as
"Metrological characteristics for
computational algorithms used in measuring systems" (Grant No.
0471-4225-40, 1984-85),
"Metrological analysis of algorithms
that process the measured information and take into consideration
the a priori knowledge about the measured object"
(Grant No. 0471-5226-40, 1985-86),
"Metrological standardization of
digital algorithms used in control and measuring systems"
(Grant No. 7550-6627-40, 1986-87),
"Standardizing precision characteristics for software used in control and
measurement" (1988-89), and
"Theoretical foundations for estimating
numerical precision of software in intellectual systems for control
and measurement" (Grant No. 7550-8170-40, 1988-90).
These research projects resulted not only in interesting scientific results
(described in numerous conference and journal papers and in detailed
technical reports), but also in the officially approved
National Recommendation document that outlined the major error
estimation algorithms (including interval methods).
As a national representative in several international organization,
he tirelessly pursued the necessity to have *guaranteed* error estimations
for indirect measurements, and made sure that the resulting
international standards for metrology (measurement theory) contain
(whenever possible) estimates and techniques that lead to guaranteed error
bounds.
In addition to being a respected scientist, Solopchenko has outstanding
leadership abilities. He is always surrounded by students and researchers
who are "infected" with his enthusiasm, and whom he actively involves in
his areas of research.
In the 1990's, he actively participated in the organization of
the International Academy of Metrological Sciences; in
recognition of his scientific and organizational efforts, he was elected a
Vice-President of this Academy. In this capacity, he actively
participated in the organization of several intervational meetings,
including the 1995 International
Workshop on Applications of Interval Computations APIC'95.
Happy birthday!
From owner-reliable_computing Fri Aug 22 09:00:30 1997
Received: by interval.usl.edu id AA22110
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 22 Aug 1997 16:00:47 -0500
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA22104
(5.65c/IDA-1.4.4 for ); Fri, 22 Aug 1997 16:00:41 -0500
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA21178; Fri, 22 Aug 97 15:00:30 MDT
Date: Fri, 22 Aug 97 15:00:30 MDT
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9708222100.AA21178 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu
Subject: contents of Reliable Computing, Vol. 3, No. 4
Sender: owner-reliable_computing
Precedence: bulk
Content of Reliable Computing, 1997, Vol. 3, No. 4
Slope Methods of Higher Order for the Inclusion
of Complex Roots of Polynomials
Ljiljana D. Petkovic, Slobodan Trickovic, and
Miodrag S. Petkovic 349 - 362
On Overestimations Produced by the Interval
Gaussian Algorithm (Dedicated to
Prof. Dr. Gerhard Heindl on the occasion
of his 60th birthday)
Jiri Rohn 363 - 368
Interval and Twin Arithmetics
Vyacheslav M. Nesterov 369 - 380
Finding Global Minima of Maximum Functions
by Using Exclusion Functions
without Derivatives
Ferenc Kalovics and Gabriella Meszaros 381 - 399
A New Approach to the Modal Regulator
Synthesis for Interval Plant with Scalar Input
Yelena M. Smagina 401 - 410
Error Reduction of the Taylor Centered Form
by Half and an Inner Estimation of the Range
Volker Stahl 411 - 420
How to Compute Interval Inclusions of
Geodetic Coordinates from
Interval Inclusions of Cartesian Coordinates
Gerhard Heindl 421 - 435
On a Theoretical Justification of the
Choice of Epsilon-Inflation in PASCAL-XSC
Vladik Kreinovich, Scott Starks,
and Guenter Mayer 437 - 445
Reviews:
Applications of Reliable Scientific Computing 447 - 452
Interval and Complexity Workshops Back-to-Back
with 1997 ACM Symposium on
Theory of Computing (STOC'97)
Luc Longpre and Martin Berz 453 - 457
Interval-Related Talks at NASA URC Conference
Monica Nogueira 459 - 460
Reliable Computing
Special Issue on Reliable Geometric Computations
Co-editors: H. Ratschek and J. Rokne 461 - 462
Best Paper Award to Zdzislaw Pawlak 463
Patrick Suppes is 75 464
P.S. My computer gave me some error message, so you may be getting this
message twice, in which I apologize. Vladik