Affine arithmetic - Simple English Wikipedia, the free encyclopedia
Affine arithmetic (AA) is a computer arithmetic which was made to improve the performance of interval arithmetic.
Background
[change | change source]Today, the interval arithmetic technology which was made by Sunaga[1] and R. Moore[2][3][4] is used in many areas including validated numerics.[5] But unfortunately, interval arithmetic is useless when numerical computation is repeated many times.[4] Therefore, many experts have studied how to overcome this weakness. Affine arithmetic is one result of this movement.
Applications
[change | change source]Affine arithmetic is available in some interval arithmetic libraries like INTLAB.[6][7] It is also used in the following fields:
Improvements
[change | change source]Some experts are trying to improve affine arithmetic. Their results are known as the extended affine arithmetic[28][29][30] or modified affine arithmetic.[31][32]
Libraries
[change | change source]This a list of libraries that supports affine arithmetic:
References
[change | change source]- ↑ T. Sunaga, Theory of interval algebra and its application to numerical analysis. (1958). RAAG memoirs, 29–46.
- ↑ Stace, Clive A. (1991-10-03). Plant Taxonomy and Biosystematics. Cambridge University Press. ISBN 978-0-521-42785-2.
- ↑ Moore, R. E. (1979). Methods and applications of interval analysis. Society for Industrial and Applied Mathematics.
- ↑ 4.0 4.1 Moore, Ramon E. (2009). Introduction to interval analysis. R. Baker Kearfott, Michael J. Cloud. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-669-6. OCLC 258333490.
- ↑ Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.
- ↑ S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.
- ↑ S.M. Rump, M. Kashiwagi: Implementation and improvements of affine arithmetic, Nonlinear Theory and Its Applications (NOLTA), IEICE, 2015.
- ↑ Femia, N., & Spagnuolo, G. (2000). True worst-case circuit tolerance analysis using genetic algorithms and affine arithmetic. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 47(9), 1285-1296.
- ↑ Lemke, A., Hedrich, L., Barke, E., & Barke, E. (2002, November). Analog circuit sizing based on formal methods using affine arithmetic. In Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design (pp. 486-489). ACM.
- ↑ Ding, T., Trinchero, R., Manfredi, P., Stievano, I. S., & Canavero, F. G. (2015). How affine arithmetic helps beat uncertainties in electrical systems. IEEE Circuits and Systems Magazine, 15(4), 70-79.
- ↑ Grimm, C., Heupke, W., & Waldschmidt, K. (2004, February). Refinement of mixed-signals systems with affine arithmetic. In Proceedings Design, Automation and Test in Europe Conference and Exhibition (Vol. 1, pp. 372-377). IEEE.
- ↑ Grimm, C., Heupke, W., & Waldschmidt, K. (2004). Analysis of mixed-signal systems with affine arithmetic. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(1), 118-123.
- ↑ Radojicic, C., Grimm, C., Schupfer, F., & Rathmair, M. (2013). Verification of mixed-signal systems with affine arithmetic assertions. VLSI Design, 2013, 5.
- ↑ Radojicic, C., & Grimm, C. (2016, June). Formal verification of mixed-signal designs using extended affine arithmetic. In 2016 12th Conference on Ph. D. Research in Microelectronics and Electronics (PRIME) (pp. 1-4). IEEE.
- ↑ Y. Kanazawa and S. Oishi (2002), "A numerical method of proving the existence of solutions for nonlinear ODEs using affine arithmetic". Proc. SCAN'02 — 10th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics.
- ↑ F. Messine and A. Mahfoudi (1998), "Use of affine arithmetic in interval optimization algorithms to solve multidimensional scaling problems". Proc. SCAN'98 — IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (Budapest, Hungary), 22–25.
- ↑ F. Messine (2002), "Extensions of affine arithmetic: Application to unconstrained global optimization". Journal of Universal Computer Science, 8 11, 992–1015.
- ↑ Vaccaro, A., Canizares, C. A., & Villacci, D. (2009). An affine arithmetic-based methodology for reliable power flow analysis in the presence of data uncertainty. IEEE Transactions on Power Systems, 25(2), 624-632.
- ↑ Gu, W., Luo, L., Ding, T., Meng, X., & Sheng, W. (2014). An affine arithmetic-based algorithm for radial distribution system power flow with uncertainties. International Journal of Electrical Power & Energy Systems, 58, 242-245.
- ↑ Wang, S., Han, L., & Wu, L. (2014). Uncertainty tracing of distributed generations via complex affine arithmetic based unbalanced three-phase power flow. IEEE Transactions on Power Systems, 30(6), 3053-3062.
- ↑ Pirnia, M., Cañizares, C. A., Bhattacharya, K., & Vaccaro, A. (2014). A novel affine arithmetic method to solve optimal power flow problems with uncertainties. IEEE Transactions on Power Systems, 29(6), 2775-2783.
- ↑ Vaccaro, A., & Canizares, C. A. (2016). An affine arithmetic-based framework for uncertain power flow and optimal power flow studies. IEEE Transactions on Power Systems, 32(1), 274-288.
- ↑ Ding, T., Bo, R., Guo, Q., Sun, H., Wu, W., & Zhang, B. (2013). A non-iterative affine arithmetic methodology for interval power flow analysis of transmission network.
- ↑ Ding, T., Cui, H., Gu, W., & Wan, Q. (2012). An uncertainty power flow algorithm based on interval and affine arithmetic. Automation of Electric Power Systems, 13.
- ↑ Pirnia, M., Cañizares, C. A., Bhattacharya, K., & Vaccaro, A. (2012, July). An affine arithmetic method to solve the stochastic power flow problem based on a mixed complementarity formulation. In 2012 IEEE Power and Energy Society General Meeting (pp. 1-7). IEEE.
- ↑ T. Kikuchi and M. Kashiwagi (2001), "Elimination of non-existence regions of the solution of nonlinear equations using affine arithmetic". Proc. NOLTA'01 — 2001 International Symposium on Nonlinear Theory and its Applications.
- ↑ M. Kashiwagi (1998), "An all solution algorithm using affine arithmetic". NOLTA'98 — 1998 International Symposium on Nonlinear Theory and its Applications (Crans-Montana, Switzerland), 14–17.
- ↑ Liao, X., Liu, K., Le, J., Zhu, S., Huai, Q., Li, B., & Zhang, Y. (2020). Extended affine arithmetic-based global sensitivity analysis for power flow with uncertainties. International Journal of Electrical Power & Energy Systems, 115, 105440.
- ↑ Messine, F., & Touhami, A. (2006). A general reliable quadratic form: An extension of affine arithmetic. Reliable Computing, 12(3), 171-192.
- ↑ Goubault, E., & Putot, S. (2008). Perturbed affine arithmetic for invariant computation in numerical program analysis. arXiv preprint arXiv:0807.2961.
- ↑ Shou, H., Lin, H., Martin, R., & Wang, G. (2003). Modified affine arithmetic is more accurate than centered interval arithmetic or affine arithmetic. In Mathematics of Surfaces (pp. 355-365). Springer, Berlin, Heidelberg.
- ↑ Shou, H., Lin, H., Martin, R. R., & Wang, G. (2006). Modified affine arithmetic in tensor form for trivariate polynomial evaluation and algebraic surface plotting. Journal of Computational and Applied Mathematics, 195(1-2), 155-171.
- ↑ Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.
Further Reading
[change | change source]Applications
[change | change source]- L. H. de Figueiredo and J. Stolfi (1996), "Adaptive enumeration of implicit surfaces with affine arithmetic". Computer Graphics Forum, 15 5, 287–296.
- W. Heidrich (1997), "A compilation of affine arithmetic versions of common math library functions". Technical Report 1997-3, Universität Erlangen-Nürnberg.
- L. Egiziano, N. Femia, and G. Spagnuolo (1998), "New approaches to the true worst-case evaluation in circuit tolerance and sensitivity analysis — Part II: Calculation of the outer solution using affine arithmetic". Proc. COMPEL'98 — 6th Workshop on Computer in Power Electronics (Villa Erba, Italy), 19–22.
- W. Heidrich, Ph. Slusallek, and H.-P. Seidel (1998), "Sampling procedural shaders using affine arithmetic". ACM Transactions on Graphics, 17 3, 158–176.
- A. de Cusatis Jr., L. H. Figueiredo, and M. Gattass (1999), "Interval methods for ray casting surfaces with affine arithmetic". Proc. SIBGRAPI'99 — 12th Brazilian Symposium on Computer Graphics and Image Processing, 65–71.
- I. Voiculescu, J. Berchtold, A. Bowyer, R. R. Martin, and Q. Zhang (2000), "Interval and affine arithmetic for surface location of power- and Bernstein-form polynomials". Proc. Mathematics of Surfaces IX, 410–423. Springer, ISBN 1-85233-358-8.
- Q. Zhang and R. R. Martin (2000), "Polynomial evaluation using affine arithmetic for curve drawing". Proc. of Eurographics UK 2000 Conference, 49–56. ISBN 0-9521097-9-4.
- N. Femia and G. Spagnuolo (2000), "True worst-case circuit tolerance analysis using genetic algorithm and affine arithmetic — Part I". IEEE Transactions on Circuits and Systems, 47 9, 1285–1296.
- R. Martin, H. Shou, I. Voiculescu, and G. Wang (2001), "A comparison of Bernstein hull and affine arithmetic methods for algebraic curve drawing". Proc. Uncertainty in Geometric Computations, 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
- A. Bowyer, R. Martin, H. Shou, and I. Voiculescu (2001), "Affine intervals in a CSG geometric modeller". Proc. Uncertainty in Geometric Computations, 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
- L. H. de Figueiredo, J. Stolfi, and L. Velho (2003), "Approximating parametric curves with strip trees using affine arithmetic". Computer Graphics Forum, 22 2, 171–179.
- C. F. Fang, T. Chen, and R. Rutenbar (2003), "Floating-point error analysis based on affine arithmetic". Proc. 2003 International Conf. on Acoustic, Speech and Signal Processing.
- A. Paiva, L. H. de Figueiredo, and J. Stolfi (2006), "Robust visualization of strange attractors using affine arithmetic". Computers & Graphics, 30 6, 1020– 1026.
Surveys
[change | change source]- L. H. de Figueiredo and J. Stolfi (2004) "Affine arithmetic: concepts and applications." Numerical Algorithms 37 (1–4), 147–158.
- J. L. D. Comba and J. Stolfi (1993), "Affine arithmetic and its applications to computer graphics". Proc. SIBGRAPI'93 — VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (Recife, BR), 9–18.
- Nedialkov, N. S., Kreinovich, V., & Starks, S. A. (2004). Interval arithmetic, affine arithmetic, Taylor series methods: why, what next?. Numerical Algorithms, 37(1-4), 325-336.