L. H. de Figueiredo and J. Stolfi, "Self-validated numerical methods and applications", Brazilian Mathematics Colloquium monographs. IMPA, Rio de Janeiro, Brazil, Jul. 1997  Home/Search   Document Details and Download   Summary   Related Articles   Check

....intervals x and is computed as (1) hi y .hi x .lo, y lo x y x z = According to the fundamental invariant, the value of quantity z lies in the interval z . Analogous formulas can be derived for multiplication, division, square root, and all other common mathematical functions [13]. The main problem of IA is overestimation, especially when intervals are correlated with each other. To illustrate the problem, suppose in (1) x = 1, 1] y = 1, 1] and the quantities x and y have the relation y = x. According to (1) z = 2, 2] while z = x y # 0 The effect of ....

....x; the corresponding coefficient x i gives the magnitude of that component. The source of the uncertainty may be either external (due to variation of the quantity, numerical approximation) or internal (due to arithmetic round off or other numerical errors committed in the computation of x ) [13]. Similar to IA, affine arithmetic also has the fundamental invariant property. For the linear operations x a x a y x and , on affine forms y x , and real number a, the resulting affine forms are easily obtained by applying (2) For any other operation f: R R, the resulting function ) ....

[Article contains additional citation context not shown here]

L. H. de Figueiredo and J. Stolfi, "Self-validated numerical methods and applications", Brazilian Mathematics Colloquium monographs. IMPA, Rio de Janeiro, Brazil, Jul. 1997

....from the problem of range explosion: as more computations are evaluated, the intervals tend to grow without bound. The problem is that correlations among variables are not captured. A recent solution to this problem is a more sophisticated interval model called a#ne arithmetic, introduced in [1]. The approach explicitly captures some of the correlations among operands, and dramatically reduces the level of pessimism in the final intervals. It has been successfully used in analog circuit sizing [6] We apply the idea to the novel prob 1bit 8bi t sign (s) exponent (e) mantissa ....

....commonly used in general purpose processors is the IEEE standard double precision or singleprecision format, which consists of three fields: sign, exponent and mantissa. Figure 1 shows the single precision floating point format, represented by 2 e bias 1. m, where e [0, 256] bias = 127, m [0, 1], and the leading 1 is implicitly specified. The precision of the floating point format is determined by the mantissa bit width, and usually 23 bit is su#cient for most applications. This is the standard mantissa bit width for single precision format. However, in application specific ....

[Article contains additional citation context not shown here]

L. H. de Figueiredo and J. Stolfi. Self-validated numerical methods and applications. Brazilian Mathematics Colloquium monograph, IMPA, Rio de Janeiro, Brazil, July 1997.

....enclosure of the object. Related work. The most simple enumeration algorithms are based on recursive uniform space subdivision. These algorithms do not take the topology of the object to be detected into account. Some algorithms subdivide until pixel size is reached to voxelize the object [6, 12, 21, 31], others follow a hybrid approach and compute for each de tected cell a linear approximation of the object. Adaptive space subdivision techniques take the curvature of the object during the subdivision process into account, followed by a linearization like in the hybrid uniform case. Adaptive ....

....of overestimation allowing a flexible refinement of the computation or taking more information about occurring errors into account. One of these approaches is affine arithmetic, that has been introduced by Stolfi and de Figuereido will be shortly presented in the next paragraph. Affine Arithmetic [21] Affine arithmetic reduces the uncontrollable blow up of intervals during the evaluation of arithmetic expressions taking dependencies of uncertainty factors of input values, approximation and rounding errors into account. Definition [21] A partially unknown quantity is represented by an ....

[Article contains additional citation context not shown here]

J. Stolfi and L. H. de Figueiredo. Self-validated numerical methods and applications, 1997.

....our cue integration technique we only need affine operations, as specified in Equation 14, other operations are also possible. A thorough description of how to do operations like reciprocation, multiplication, exponentiations, trigonometry, and even how to define a new operation, can be found in [38]. An affine form that is the result of an operation on other affine forms shares its noise variables with the affine forms of the operands. As a result, and in contrast to interval arithmetic, affine forms preserve interdependencies between values from intermediate computations. After a series of ....

J. Stolfi and L. Figueiredo. Self-Validated Numerical Methods and Applications. 21 Colquio Brasileiro de Matemtica, IMPA, 1997.

....analysis and optimization [9] and computer graphics [25, 10] This approach suffers from overestimation of bounds, and the complete loss of information on how bounds in multidimensional intervals are correlated. More recently, affine arithmetic has been developed to overcome these shortcomings [1, 26]. It has previously been applied to numerical optimization [5, 17, 13] In this paper we apply affine arithmetic to embed deformable models within a statistical framework. This approach allows us to avoid making assumptions about the probability distribution functions, unlike most previous ....

....approximation for the valid range. We then introduce an extra independent noise symbol is to carry the introduced error, thus keeping the interval valid. A thorough description on how to do the appropriate operations (reciprocate, multiplications, exponentials, trigonometric, etc. can be found in [26]. We now show how to obtain the Gaussian parameters c and c from an affine form describing the generalized cue force f g;c , so that we can use it in a maximum likelihood estimator (MLE) 4. Obtaining a Gaussian random variable from an affine form After using affine arithmetic on the image ....

[Article contains additional citation context not shown here]

J. Stolfi and L. Figueiredo. Self-Validated Numerical Methods and Applications. 21 o Coloquio Brasileiro de Matematica, IMPA, 1997.

....as a upper 25 bound, and 0 can only appear as a lower bound. With this convention, we find that the IEEE standard facilitates interval arithmetic to a remarkable extent. However, we realize that the beauty of the standard is in the eye of the beholder: other researchers in interval arithmetic [19] criticize the signed zeros as follows: While it is possible to concoct examples where this feature saves an instruction or two, in the vast majority of applications this value is an annoying distraction and a source of subtle bugs. 5.3 Optimal IEEE Approximations of Interval Arithmetic In ....

J. Stolfi and L. de Figueiredo. Self-validated numerical methods and applications, 1997.

....[c, d] a d,b c] c, d] min(ac,ad,bc,bd) max(ac,ad,bc,bd) a, b] c, d] a, b] 1 d,1 c] provided 0 ## [c, d] with special care to round lower bounds downwards and upper bounds upwards. Similar formulas can be given for extending the elementary functions to intervals [9]. Once we have interval formulas for all primitive operations and functions, we then automatically have formulas for all functions that can be obtained One of the original motivations for the creation of interval arithmetic was automatic, a posteriori, roundoff error analysis: real numbers ....

....above, for both affine and non affine operations, do not take into account rounding errors. In practice, rounding errors are handled by adding a new noise symbol to carry them or by absorbing them into the approximation error term z k e k , in the case of non affine operations. For details, see [9]. 3.3. SELECTING A GOOD AFFINE APPROXIMATION As discussed above, to compute with affine arithmetic we must find a good affine approximation f for each primitive non affine operation f . When we write f as a function of the noise symbols in the input forms x and y, a b u a b Figure 4. ....

[Article contains additional citation context not shown here]

Stolfi, J. and L. H. de Figueiredo: 1997, Self-Validated Numerical Methods and Applications. Rio de Janeiro: Monograph for 21st Brazilian Mathematics Colloquium, IMPA. Available at ftp://ftp.tecgraf.puc-rio.br/pub/lhf/doc/cbm97.ps.gz.

No context found.

J. Stolfi and L. H. de Figueiredo, Self-Validated Numerical Methods and Applications. Rio de Janeiro: Monograph for 21st Brazilian Mathematics Colloquium, IMPA, (1997). Available at ftp://ftp.tecgraf. puc-rio.br/pub/lhf/doc/cbm97.ps.gz.

....midpoint of P may be difficult to compute; a much simpler choice for the splitting point is the point in P corresponding to the midpoint of T . We shall adopt this choice in the sequel. 4 Affine arithmetic Affine arithmetic (AA) was introduced in SIBGRAPI 93 [2] as a tool for validated numerics [20]. Since then, AA has been applied to the robust solution of several graphics problems [4,6,7,11,12] where it has successfully replaced interval arithmetic [16] In AA, a quantity x is represented as an affine form, x = x 0 x 1 1 xn n ; which is a polynomial of degree 1 in ....

....x lies in the interval [x 0 r x ; x 0 r x ] where r x = jx 1 j jx n j. In other words, quantities in AA also naturally represent intervals, and so AA can replace interval arithmetic [16] The basic arithmetic operations and elementary functions can be extended to handle affine forms [20]. Affine operations (translation, scale, addition, and subtraction) are straightforward. Non affine operations, such as multiplication, square root, and trigonometric functions, use a good affine approximation plus an error term (which creates a new noise symbol) So, the result of a function f ....

J. Stolfi and L. H. de Figueiredo. Self-Validated Numerical Methods and Applications. Monograph for 21st Brazilian Mathematics Colloquium, IMPA, Rio de Janeiro, 1997. Available at ftp://ftp.tecgraf.puc-rio.br/ pub/lhf/doc/cbm97.ps.gz.

....to contain all the values obtained by operating with all the numbers in the input intervals. This is easy to do for the elementary operations and functions [9] Implementing interval arithmetic in floating point machine arithmetic is not difficult, although care has to be taken with roundings [20]. There are several packages for interval arithmetic available in the Internet [21] Specially convenient are packages in languages that allow operator overloading, such as C and Fortran 90, because then algebraic expressions can be written in the familiar way and inclusion functions are ....

J. Stolfi, L. H. de Figueiredo, Self-Validated Numerical Methods and Applications, Monograph for 21st Brazilian Mathematics Colloquium, IMPA, Rio de Janeiro, 1997, available at ftp://ftp.tecgraf.puc-rio.br/ pub/lhf/doc/cbm97.ps.gz.

....to contain all the values obtained by operating with all the numbers in the input intervals. This is easy to do for the elementary operations and functions [24] Implementing interval arithmetic in floating point machine arithmetic is not difficult, although care has to be taken with roundings [31]. There are several packages for interval arithmetic available in the Internet [20] Specially convenient are packages in languages that allow operator overloading, such as C and Fortran 90, because then algebraic expressions can be written in the familiar way and inclusion functions are ....

J. Stolfi and L. H. de Figueiredo. Self-Validated Numerical Methods and Applications. Monograph for 21st Brazilian Mathematics Colloquium, IMPA, Rio de Janeiro, 1997. Available at ftp://ftp.tecgraf.puc-rio.br/ pub/lhf/doc/cbm97.ps.gz.

....(translation, scale, addition, and subtraction) are straightforward. Non affine operations, such as multiplication and square root, use a good affine approximation plus an error term (which creates a new noise symbol) For details of how AA (and IA) operations can be implemented, see reference [21]. The key feature of AA is that the same noise symbol may contribute to the uncertainty of two or more quantities (inputs, outputs, or intermediate results) arising in the evaluation of an expression. The sharing of a noise symbol i by two affine forms x and y indicates some partial ....

....batch implementation under Linux. Preliminary results using this implementation are very promising, and will be reported elsewhere. AA did not give the best results in all cases. AA suffers from an overestimation problem for some primitive operations, such as the square operation (y x 2 ) [21]. Accordingly, IA was faster for the surfaces that contain many square terms, with no negative correlation. Range estimates given by AA are not always better than those given by IA. For the function in Figure 2, the range estimate computed by AA is actually larger than the range estimate computed ....

[Article contains additional citation context not shown here]

J. Stolfi and L. H. de Figueiredo. Self-Validated Numerical Methods and Applications. Monograph for 21st Brazilian Mathematics Colloquium, IMPA, Rio de Janeiro, 1997.

Online articles have much greater impact   More about CiteSeer   Add search form to your site   Submit documents   Feedback  


CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute