Re: IEEE Standard 1788-2015
In the standard there are interval operations that
allow you to obtain x-x=0, these are the cancel plus/minus
operations. However, the cancel +/- are not "operations" in the
sense of algebra. I would suggest that the cancel plus/minus "operations"
are included in the basic standard.
S. Markov
PS. Algebraic operations have to be defined for all
intervals, whereas the cancel +/- are not. It is a pity that
the inner operations (proposed by me and Nate) were not
included in the standard. The inner +/- operations are
operations in algebraic sense.
On 26 Sep 2015 at 17:10, Kreinovich, Vladik wrote:
From: "Kreinovich, Vladik" <vladik@xxxxxxxx>
To: "Kreinovich, Vladik" <vladik@xxxxxxxx>,
Mehran Mazandarani <me.mazandarani@xxxxxxxxx>,
stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>,
"Andrzej Piegat" <apiegat@xxxxxxxxxxxxx>
Subject: RE: IEEE Standard 1788-2015
Date sent: Sat, 26 Sep 2015 17:10:56 +0000
> On 1): we are talking about the problem that I mentioned in my first very email
> reply: we have a function f(x1,…,xn) and n intervals, we need to find a range
> of this function on these intervals.
>
> If n is fixed, then we have a polynomial-time algorithm – but the power of the
> corresponding polynomial grows with n.
>
> From: stds-1788@xxxxxxxx [mailto:stds-1788@xxxxxxxx] On Behalf Of Kreinovich,
> Vladik
> Sent: Saturday, September 26, 2015 10:33 AM
> To: Mehran Mazandarani <me.mazandarani@xxxxxxxxx>; stds-1788
> <stds-1788@xxxxxxxxxxxxxxxxx>; Andrzej Piegat <apiegat@xxxxxxxxxxxxx>
> Subject: RE: IEEE Standard 1788-2015
>
> 1) Yes, it would be desirable to compute the exact range all the time and
> to avoid overestimation, but it is known theorem that computing the exact range
> of a function under interval uncertainty is NP-hard, even for quadratic
> functions, so if we want to get guaranteed bounds, excess width is inevitable,
> i.e., if we want to always get an enclosure, an interval always containing the
> exact range, it is inevitable that we have an enclosure which is sometimes
> different from the exact range.
> 2) The original example of x-x when x is [1,3] (and a similar example of
> x/x) are based on a major misunderstanding of interval computations which is,
> unfortunately, rather common: that interval computations means replacing each
> operation with numbers by a corresponding operation with intervals. This
> so-called na"ive interval computations was never advocated by anyone, the very
> first 1966 book by Moore has exactly this example of x-x to show that this is
> NOT the way to go. A proper way – as shown in any textbook or survey on
> interval computations and implemented in all the packages – is to first check
> monotonicity and then use centered form if the function is not monotonic.
> Monotonicity can be checked if we apply automatic differentiation to the
> expression and then use na"ive interval computations to find the range of the
> resulting derivative. If the resulting interval is always non-negative or
> always non-positive, the function is monotonic and its range is easy to compute
> by simply computing the values at endpoints. When we apply this to x-x,
> interval computations lead to 0 range, NOT to [-2,2]. Same with x/x.
>
> From:stds-1788@xxxxxxxx [mailto:stds-1788@xxxxxxxx] On Behalf Of Mehran
> Mazandarani
> Sent: Saturday, September 26, 2015 6:19 AM
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>; Andrzej Piegat
> <apiegat@xxxxxxxxxxxxx>
> Subject: IEEE Standard 1788-2015
>
> Dear John, Vladik, Michel, and IC members
> Thank you for your kind reply.
> I am writing to you regarding the previous emails about that section in Std.
> 1788 which deals with operations for interval arithmetic.
> As I mentioned, based on the Std. 1788-2015 we may obtain results which lead to
> values that are not possible actually.
> Michel told that it is because of dependency issue, and that Moore's arithmetic
> is indeed a worst-case arithmetic -- but this allows it to *guarantee* that the
> computed result encloses any possible actual result.
> Then, he told When an interval programmer writes a program to compute a
> particular function, which could (in the point-function context) be written as
> an
> algebraic expression where certain variables may appear multiple times,
> the programmer may take advantage of specific knowledge -- in particular,
> monotonicity properties -- to compute a tighter enclosure than blindly
> evaluating the expression using Moore arithmetic.
> 1. Using Moore's approach leads to obtain values which may not be possible,
> i.e. impossible values. So, it makes us to analyze, decide, and design systems
> and processes with too high costs and probably too complex. That all of these
> are because of values which are impossible, i.e. they will not happen.
> 2. The standard should be based on an approach which makes us be assured in at
> least some future development. This is while as you can see the attachment,
> using advantage of specific knowledge we get to what I termed it Restoration
> issue.
> Additionally, we are just considering very simple cases, because the
> cases themselves have their own issues of obtaining real possible
> results/values, let alone problems related to differential equations and
> defining derivatives.
> I recommend to rethink about the section of Std. 1788-2015 which deals with
> fourth basic operations in order to avoiding what will mislead us in so many
> problems.
> Comments are welcome.
> Thank you so much for your kind attention and consideration.
> Warmest regards,
>
> Mehran Mazandarani
> Department of Electrical Engineering
> Ferdowsi University of Mashhad, Mashhad, Iran.
> homepage:http://mehran.mazandarani.fumblog.um.ac.ir/
> http://works.bepress.com/mehran_mazandarani
> IEEE Member, me.mazandarani@xxxxxxxx
>
>
>
>
>
>
>
>
Prof. Svetoslav Markov, DSci, PhD,
Dept. "Math Modelling & Num Analysis", phone: +359-2-979-2876
Inst. of Mathematics and Informatics, fax: +359-2-971-3649
Bulgarian Academy of Sciences, e-mail: smarkov@xxxxxxxxxx
"Acad. G. Bonchev" st., block 8,
BG-1113 Sofia, BULGARIA mobile (gsm): 08888 24567
URL: http://www.math.bas.bg/~bio/
URL: http://www.biomath.bg/
www.biomath.bg/2015/
http://www.biomathforum.org/biomath/