Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giải pháp song song cho các hệ phương trình phi tuyến tổng quát thưa quy mô lớn
Tóm tắt
Trong việc giải quyết các vấn đề ứng dụng, nhiều hệ phương trình phi tuyến quy mô lớn dẫn đến các ma trận Jacobian thưa. Những hệ phi tuyến như vậy được gọi là hệ phi tuyến thưa. Tính không đều của vị trí các phần tử khác không của một ma trận thưa tổng quát làm cho việc ánh xạ tính toán ma trận thưa sang các bộ xử lý đa luồng thật khó khăn để thực hiện xử lý song song một cách cân bằng. Để khắc phục khó khăn này, chúng tôi đề xuất một sơ đồ lưu trữ mới cho các ma trận thưa tổng quát trong bài báo này. Với sơ đồ lưu trữ mới, chúng tôi phát triển các thuật toán song song để giải quyết các hệ phương trình thưa tổng quát quy mô lớn bằng các phương pháp Newton/Phân hoạch tổng quát theo khoảng, những phương pháp này tìm ra tất cả các nghiệm số một cách đáng tin cậy trong một miền nhất định. Ở Mục 1, chúng tôi cung cấp một giới thiệu về vấn đề được đề cập và các phương pháp Newton theo khoảng. Ở Mục 2, một số sơ đồ lưu trữ hiện đang được sử dụng cho các hệ phi tuyến thưa được xem xét. Ở Mục 3, các sơ đồ chỉ mục mới để lưu trữ các ma trận tổng quát thưa được báo cáo. Ở Mục 4, chúng tôi trình bày một thuật toán song song để đánh giá một ma trận Jacobian thưa tổng quát. Ở Mục 5, chúng tôi trình bày một thuật toán song song để giải quyết hệ phương trình tuyến tính theo khoảng tương ứng bằng sơ đồ tiền điều kiện tất cả các hàng. Các kết luận và công việc trong tương lai sẽ được thảo luận trong Mục 6.
Từ khóa
#hệ phi tuyến #ma trận Jacobian thưa #thuật toán song song #phương pháp Newton theo khoảng #sơ đồ lưu trữ thưaTài liệu tham khảo
Alefeld G, Herzberger J. Introduction to Interval Computations. Academic Press, New York, 1983.
Dongarra Jet al. Solving linear systems on vector and shared memory computers.SIAM, 1991.
Duff I. Direct Methods for Sparse Matrices. Oxford University Press, 1986.
Duff I. Sparse matrix test problems.ACM Trans. Math. Software, 1989, 15(1): 1–14.
Gan Q, Yang Q, Hu C. Parallel all-row preconditioned interval linear solver for nonlinear equations on multiprocessor.Parallel Computing, 1994, 20(9): 1249–1268.
Hansen E R. On solving systems of equations using interval arithmetic.Math. Comp., 1968, 22: 374–384.
Hansen E R. Interval forms of Newton’s method.Computing, 1978, 20: 153–163.
Hansen E R, Sengupta S. Bounding solutions of systems of equations using interval arithmetic.BIT, 1981, 21: 203–211.
Hu C. Optimal preconditioners for interval Newton methods. Ph.D. dissertation., The University of Southwestern Louisiana, 1990.
Hu C, Kearfott B. A pivoting scheme for the interval Gauss-Seidel Method. InApproximation, Optimization and Computing, Eleevier Science Publishers, pp. 97–102, 1990.
Hu C, Bayoumi M, Kearfott B, Yang Q. A parallelized algorithm for the preconditioned interval Newton method. InProc. SIAM 5th Conf. on Paral. Proc. for Sci. Comp., 1991.
Hu C. On parallelization of interval Newton method on distributed-memory multiprocessors. InProc. SIAM 6th Conf. on Paral. Proc. for Sci. Comp., 1993, pp. 623–627.
Hu C, Sheldon J, Kearfott B, Yang Q. On the optimization of INTBIS on a Cray YMP.Reliable Computing, 1995, 1(3): 265–274.
Kearfott R B. Abstract generalized bisection and a cost bound.Math. Comp., 1987, 49(179): 187–202.
Kearfott R B, Novoa M. INTBIS, a program for generalized bisection.ACM Trans. Math. Software, 1990.
Kearfott R B. Preconditioners for the interval Gauss-Seidel method.SIAM J. Num. Anal., 1990, 27(3): 809–822.
Kearfott R B, Hu C, Novoa M. A review of preconditioners for the interval Gauss-Seidel method.Interval Computations., 1991, I: 59–85.
Kearfott R B, Dawande M, Du K, Hu C. Algorithm 737: INTLIB: A portable Fortran-77 interval standard-function library.ACM Trans. Math. Software, 1994, 20(4): 447–459.
Knuth D. Fundamental Algorithms. InThe Art of Computer Programming, Vol. 1. Addison Wesley, 1968.
Moore R E. Methods and applications of interval analysis.SIAM, 1979.
PCGPAL User’s Guide. Scientific Computing Associates, Inc., New Haven.
Press Wet al. Numerical Recipes, second edition. Cambridge, 1992.
Schnepper C, Stadtherr M. Application of a parallel interval Newton/generalized bisection algorithm to equation-based chemical process flowsheeting.Interval Computations, 1993, (4): 40–64.