Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Đại số ma trận hiệu quả với độ chính xác cao trên các kiến trúc song song cho tối ưu hóa tổ hợp phi tuyến
Tóm tắt
Chúng tôi cung cấp một minh chứng đầu tiên cho ý tưởng rằng các thuật toán dựa trên ma trận cho các bài toán tối ưu hóa tổ hợp phi tuyến có thể được thực hiện một cách hiệu quả. Các thuật toán như vậy chủ yếu được hình thành bởi các nhà khoa học máy tính lý thuyết để chứng minh tính hiệu quả. Chúng tôi có khả năng chứng minh tính thực tiễn của phương pháp của mình bằng cách phát triển một ứng dụng trên một kiến trúc song song khổng lồ, và khai thác các ứng dụng song song có khả năng mở rộng và hiệu quả cho đại số tuyến tính siêu chính xác. Thêm vào đó, chúng tôi đã phác thảo và thực hiện các thay đổi về thuật toán và mã hóa cần thiết để giải quyết các vấn đề lớn hơn nhiều bậc, liên quan đến những giới hạn của khả năng mở rộng từ góc độ mức tiêu thụ bộ nhớ, hiệu quả tính toán, độ tin cậy và khả năng kết nối.
Từ khóa
#tối ưu hóa tổ hợp phi tuyến #thuật toán ma trận #kiến trúc song song #đại số tuyến tính #hiệu suất tính toánTài liệu tham khảo
Alam, S., Barrett, R., Bast, M., Fahey, M.R., Kuehn, J., McCurdy, C., Rogers, J., Roth, P., Sankaran, R., Vetter, J.S., Worley, P., Yu, W.: Early evaluation of IBM BlueGene/P, SC ’08. In: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, pp 1–12 (2008)
Almási G., Archer C., Castaños J.G., Gunnels J.A., Erway C.C., Heidelberger P., Martorell X., Moreira J.E., Pinnow K., Ratterman J., Steinmacher-Burow B.D., Gropp W., Toonen B.: Design and implementation of message-passing services for the Blue Gene/L supercomputer. IBM. J. Res. Dev. 49(2–3), 393–406 (2005)
ARPREC. http://crd.lbl.gov/~dhbailey/mpdist/mpdist.html
Bailey D.H.: High-precision arithmetic in scientific computation. Comput. Sci. Eng. 7(3), 54–61 (2005)
Bailey, D.H., Borwein, J.M.: Highly Parallel, High-Precision Numerical Integration. LBNL-57491 (2005)
Berstein Y., Lee J., Maruri-Aguilar H., Onn S., Riccomagno E., Weismantel R., Wynn H.: Nonlinear matroid optimization and experimental design. SIAM J. Discret. Math. 22(3), 901–919 (2008)
Berstein, Y., Lee, J., Onn, S., Weismantel, R.: Parametric nonlinear discrete optimization over well-described sets and matroid intersections. Math. Program. (to appear)
Buttari A., Dongarra J., Langou J., Langou J., Luszczek P., Kurzak J.: Mixed precision iterative refinement techniques for the solution of dense linear systems. Int. J. High. Perform. Comput. Appl. 21(4), 457–466 (2007)
Chiu, G.L.-T., Gupta, M., Royyuru, A.K. (guest eds.): Blue Gene. IBM J. Res. Dev. 49(2/3) (2005)
Choi J., Dongarra J., Ostrouchov S., Petitet A., Walker D., Whaley C.: Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Sci. Program. 5(3), 173–184 (1996)
De Loera, J., Haws, D.C., Lee, J., O’Hair, A.: Computation in multicriteria matroid optimization. ACM J. Exp. Algorithmics 14, Article No. 8, (2009)
Demmel, J.: The future of LAPACK and ScaLAPACK, PARA 06: workshop on State-of-the-Art. In: Scientific and Parallel Computing, Umea, Sweden, 18–21 June 2006. http://www.cs.berkeley.edu/~demmel/cs267_Spr07/future_sca-lapack_CS267_Spr07.ppt
Eisinberg A., Fedele G., Imbrogno C.: Vandermonde systems on equidistant nodes in [0, 1]: accurate computation. Appl. Math. Comput. 172, 971–984 (2006)
Eisinberg A., Franzé G., Pugliese P.: Vandermonde matrices on integer nodes. Numerische Mathematik 80(1), 75–85 (1998)
Fries A., Hunter W.G.: Minimum aberration 2k-p designs. Technometrics 22, 601–608 (1980)
Harvey, N.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. (2010, to appear)
Higham N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2002)
IBM Blue Gene Team: Overview of the IBM Blue Gene/P project, IBM J. Res. Dev., v52, (2008), 199–220
Lee, J.: A First Course in Combinatorial Optimization. Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge (2004)
Lee J., Ryan J.: Matroid applications and algorithms. INFORMS (formerly ORSA) J. Comput. 4, 70–98 (1992)
mStirling.c. http://ftp.bioinformatics.org/pub/pgetoolbox/addins/src/mStirling.c
Mulmuley K., Vazirani U.V., Vazirani V.V.: Matching is as easy as matrix inversion. Combinatorica 7, 105–113 (1987)
Oxley J.G.: Matroid Theory. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1992)
Pistone, G., Riccomagno, E., Wynn, H.P.: Algebraic Statistics. Monographs on Statistics and Applied Probability, vol. 89. Chapman & Hall/CRC, Boca Raton (2001)
Recski A.: Matroid theory and its applications in electric network theory and in statics. Springer, Berlin (1989)
Tweddle, I.: James Stirling’s methodus differentialis: an annotated translation of Stirling’s text. In: Sources and Studies in the History of Mathematics and Physical Sciences, Springer (2003)
van de Geijn R.A., Watts J.: SUMMA: scalable universal matrix multiplication algorithm. Concurr. Pract. Experience 9(4), 255–274 (1997)
VanInverse.m. http://www.mathworks.com/matlabcentral/files/8048/VanInverse.m
Wu H., Wu C.F.J.: Clear two-factor interactions and minimum aberration. Ann. Stat. 30, 1496–1511 (2002)