Next:
1 Motivation
Up:
Generalized Interval Arithmetic M.Sc. Thesis
Previous:
Generalized Interval Arithmetic M.Sc. Thesis
Contents
1 Motivation
1.1 Sampling
1.2 Implicit Equations
1.3 Relations
1.4 Numerical Round-Off
1.5 Computability
1.6 Perseverance
1.7 Outline
2 Numbers
2.1 Integers
2.2 Rational Numbers
2.3 Real Numbers
2.4 Complex Numbers
2.5 Floating Point
2.5.1 Infinity
2.5.2 NAN
2.5.3 Rounding
2.5.4 Algebraic Properties
2.6 Extended Real Numbers
2.6.1 Hyperreal Numbers
2.6.2 Type Conversion
2.6.3 Infinity Unveiled
2.7 Interval Arithmetic
2.7.1 Syntax
2.7.2 Order
2.7.3 Inclusion Property
2.7.4 Interval Extension
2.7.5 Algebraic Properties
2.8 Real Interval Arithmetic
2.9 Generalized Interval Arithmetic
2.9.1 Unification
2.9.2 Three Valued Logic
2.9.3 Linear Intervals
2.9.4 Constant Intervals
2.9.5 Quadratic Intervals
2.9.6 Multi-Dimensional Linear Intervals
2.9.7 Functional Intervals
2.9.8 Symbolic Intervals
2.10 Generalized Floating Point Interval Arithmetic
2.11 Interval Function Domains
2.11.1 Interval Inclusion
2.11.2 Interval Extension
2.11.3 Domain Descriptions
2.11.4 Conjunctions
2.11.5 Simplicity
2.12 Property Tracking
2.12.1 Properties
2.12.2 Interval Inclusion and Extension
2.12.3 Systems
2.13 Interval Sets
2.13.1 Interval Inclusion and Extension
2.13.2 Bumpy Functions
2.14 Variants
2.15 Real Representations
2.15.1 Dedekind Cuts
2.15.2 Cauchy Sequences
2.15.3 Decimal Expansions
2.15.4 Continued Fractions
2.15.5 Converging Intervals
2.15.6 Redundant Decimal Expansions
2.15.7 Redundant Continued Fractions
2.15.8 Generalized Interval Arithmetic
3 Arithmetic
3.1 Floating Point
3.1.1 Exact Functions
3.1.2 Constant Functions
3.1.3 Provided Functions
3.1.4 Accurate Functions
3.1.5 Argument Reduction
3.1.6 Basic Methods
3.2 Constant Interval Arithmetic
3.2.1 Constant Functions
3.2.2 Interpolating Polynomials
3.2.3
Charts
3.2.4 Constant Functions
3.2.5 Optimality
3.2.6 Piecewise Models
3.2.7
Charts
3.2.8 Piecewise Constant Functions
3.2.9 Examples with Piecewise Constant Functions
3.2.10 Monotonically Increasing Functions
3.2.11 Monotonically Decreasing Functions
3.2.12 Lower Bounds
3.2.13 Examples with Monotonic Functions
3.2.14 Examples with Piecewise Monotonic Functions
3.2.15 Periodic Functions
3.2.16 Partial Functions
3.2.17 Examples with a Partial Function
3.2.18 Discontinuous Functions
3.2.19 Example with a Discontinuous Function
3.2.20 Bumpy Functions
3.2.21 Examples with Bumpy Functions
3.2.22 Common Binary Functions
3.2.23 Binary Functions
3.2.24
Charts
3.2.25 Examples with a Binary Function
3.2.26 Partial Binary Functions
3.2.27 Example with a Partial Binary Function
3.2.28 Monotonically Increasing, Decreasing Functions
3.3 Linear Interval Arithmetic
3.3.1 Interpolating Polynomials
3.3.2
Charts
3.3.3 Optimality
3.3.4 Piecewise Models
3.3.5
Charts
3.3.6 Monotonic Sections
3.3.7 Linear Functions
3.3.8 Example with a Linear Function
3.3.9 Examples with a Piecewise Linear Function
3.3.10 Concave Up Functions
3.3.11 Concave Down Functions
3.3.12 Lower Bounds
3.3.13 Example with a Concave Function
3.3.14 Example with a Piecewise Concave Function
3.3.15 Periodic Functions
3.3.16 Partial Functions
3.3.17 Examples with a Partial Function
3.3.18 Discontinuous Functions
3.3.19 Examples with a Discontinuous Function
3.3.20 Bumpy Functions
3.3.21 Examples with Bumpy Functions
3.3.22 Binary Functions: Two-Step Method
3.3.23
Charts
3.3.24 Examples with Binary Functions
3.3.25 Binary Functions: One-Step Method
3.3.26 Examples with a Binary Function
3.3.27 Partial Binary Functions
3.3.28 Examples with a Binary Partial Function
3.3.29 Concave Up, Down Functions
3.3.30 Floating Point
3.4 Polynomial Interval Arithmetic
3.4.1 Interpolating Polynomials
3.4.2
Charts
3.4.3 Optimality
3.4.4 Piecewise Models
3.4.5
Charts
4 Graphs
4.1 Graphs
4.1.1 Rendering
4.1.2 Batch Rendering
4.1.3 Progressive Rendering
4.1.4 Syntax
4.1.5 Notation
4.2 Basic Rendering
4.2.1 Constant Interval Arithmetic
4.2.2 Sequential Rendering
4.2.3 Pixel Testing
4.2.4 Subpixel Testing
4.2.5 Exhaustive Subpixel Testing
4.2.6 Continuity-Based Testing
4.2.7 Linear Interval Arithmetic
4.2.8 Sequential Rendering
4.3 Optimization: Function Rendering
4.3.1 Optimization: Super-Pixel Rendering
4.3.2 Constant Interval Arithmetic
4.3.3 Linear Interval Arithmetic
4.3.4 Cut Heuristics
4.3.5 Examples of Cutting Heuristics
4.4 Optimization: Caching
4.5 Optimization: Removing Conditionals
4.6 Alternative Formalisms
4.7 Other Work
4.7.1 Sampling
4.7.2 Line Tracing
4.7.3 Extended Interval Arithmetic
4.7.4 Derivative-Based Methods
4.7.5 Hansen's Linear Interval Arithmetic
4.8 Example Renderings
5 Conclusion
5.1 Interval Techniques
5.2 Graphing
5.3 Future Work
References
About this document ...
Next:
1 Motivation
Up:
Generalized Interval Arithmetic M.Sc. Thesis
Previous:
Generalized Interval Arithmetic M.Sc. Thesis
Jeff Tupper
March 1996