アフィン演算

数値解析・精度保証付き数値計算においてアフィン演算（アフィンえんざん、英: affine arithmetic）は区間演算における区間幅の増大を抑止するために作られた演算方式である^[1]。

背景

須永照雄^[2]や R. Moore^[3]^[4]^[5]によって開発された区間演算は現代では精度保証付き数値計算を含む様々な分野に応用されているが^[1]^[6]、計算を繰り返すと区間幅が増大してしまい、有意義な結果が得られなくなるという致命的な弱点があった (これが区間演算・精度保証付き数値計算の普及を妨げる一因となっている)^[1]。そこで多くの技術者・研究者たちがこの難点を克服すべく研究を積み重ねてきた。アフィン演算はその成果物の一つである。

応用

アフィン演算はMATLAB/GNU Octaveで作られた区間演算ライブラリINTLAB^[7]^[8]に搭載されている他、

常微分方程式の数値解法^[1]^[9]^[10]
求根アルゴリズム^[11]^[12]
最適化問題^[13]^[14]
混合信号 (英: mixed signal systems)^[15]^[16]^[17]^[18]
電力潮流 (英: power flow)^[19]^[20]^[21]^[22]^[23]^[24]^[25]^[26]
電気回路または電子回路^[27]^[28]^[29]^[30]^[31]

にも活用されている。

改良

アフィン演算をよりよくしようという研究もおこなわれており、これらの手法は拡張アフィン演算 (英: extended affine arithmetic)^[32]^[33]^[34]^[35]、または変形アフィン演算 (英: modified affine arithmetic)^[36]^[37]などと総称される。

アフィン演算が使える数値計算ライブラリ

INTLAB
kv - GitHub (C++によるライブラリ)
Libaffa (C++によるライブラリ)
- libaffa - GitHub
YalAA (C++によるライブラリ)
- yalaa - GitHub
ASOL
- asol - GitHub

出典

[脚注の使い方]

^ ^a ^b ^c ^d 『精度保証付き数値計算の基礎』大石進一編著、コロナ社、2018年。
^ T. Sunaga, Theory of interval algebra and its application to numerical analysis. (1958). RAAG memoirs, 29–46.
^ Interval Analysis. Englewood Cliff, New Jersey, USA: Prentice-Hall. (1966). ISBN 0-13-476853-1.
^ Moore, R. E. (1979). Methods and applications of interval analysis. Society for Industrial and Applied Mathematics.
^ Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathematics (SIAM). (2009). ISBN 0-89871-669-1.
^ 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.
^ 柏木啓一郎, & 柏木雅英. (2011). 平均値形式とアフィン演算を用いた常微分方程式の精度保証法. 日本応用数理学会論文誌, 21(1), 37-58.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 三島和博. (2011). アフィン演算を用いた非線形回路のすべての解を求めるアルゴリズム. 中央大学大学院研究年報理工学研究科編, 41.
^ 小林玄宙, 三島和博, & 山村清隆. (2012). A-2-14 アフィン演算と LP 縮小を用いた非線形回路の全解探索法 (A-2. 非線形問題, 一般セッション). 電子情報通信学会総合大会講演論文集, 2012, 59.
^ 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.
^ 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.
^ IRDB:00931/0000195611
^ 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. en:Journal of computational and applied mathematics, 195(1-2), 155-171.

参考文献

応用に関する文献

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.

解説記事

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.

外部リンク

Affine Arithmetic について (PDF)

この項目は、応用数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[oishi-1] 『精度保証付き数値計算の基礎』大石進一編著、コロナ社、2018年。

[2] T. Sunaga, Theory of interval algebra and its application to numerical analysis. (1958). RAAG memoirs, 29–46.

[3] Interval Analysis. Englewood Cliff, New Jersey, USA: Prentice-Hall. (1966). ISBN 0-13-476853-1.

[4] Moore, R. E. (1979). Methods and applications of interval analysis. Society for Industrial and Applied Mathematics.

[5] Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathematics (SIAM). (2009). ISBN 0-89871-669-1.

[6] Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.

[7] S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.

[8] S.M. Rump, M. Kashiwagi: Implementation and improvements of affine arithmetic, Nonlinear Theory and Its Applications (NOLTA), IEICE, 2015.

[9] 柏木啓一郎, & 柏木雅英. (2011). 平均値形式とアフィン演算を用いた常微分方程式の精度保証法. 日本応用数理学会論文誌, 21(1), 37-58.

[10] 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.

[11] 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.

[12] 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.

[13] 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.

[14] F. Messine (2002), "Extensions of affine arithmetic: Application to unconstrained global optimization". Journal of Universal Computer Science, 8 11, 992–1015.

[15] 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.

[16] 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.

[17] Radojicic, C., Grimm, C., Schupfer, F., & Rathmair, M. (2013). Verification of mixed-signal systems with affine arithmetic assertions. VLSI Design, 2013, 5.

[18] 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.

[19] 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.

[20] 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.

[21] 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.

[22] 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.

[23] 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.

[24] 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.

[25] 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.

[26] 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.

[27] 三島和博. (2011). アフィン演算を用いた非線形回路のすべての解を求めるアルゴリズム. 中央大学大学院研究年報理工学研究科編, 41.

[28] 小林玄宙, 三島和博, & 山村清隆. (2012). A-2-14 アフィン演算と LP 縮小を用いた非線形回路の全解探索法 (A-2. 非線形問題, 一般セッション). 電子情報通信学会総合大会講演論文集, 2012, 59.

[29] 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.

[30] 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.

[31] 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.

[32] 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.

[33] IRDB:00931/0000195611

[34] Messine, F., & Touhami, A. (2006). A general reliable quadratic form: An extension of affine arithmetic. Reliable Computing, 12(3), 171-192.

[35] Goubault, E., & Putot, S. (2008). Perturbed affine arithmetic for invariant computation in numerical program analysis. arXiv preprint arXiv:0807.2961.

[36] 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.

[37] Shou, H., Lin, H., Martin, R. R., & Wang, G. (2006). Modified affine arithmetic in tensor form for trivariate polynomial evaluation and algebraic surface plotting. en:Journal of computational and applied mathematics, 195(1-2), 155-171.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]