Parallel Jacobi-Davidson Algorithms and Software
Developments for Polynomial Eigenvalue
Problems in Quantum Dot Simulation

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：18.218.127.141

姓名

魏子豪(Zih-Hao Wei) 查詢紙本館藏

畢業系所

數學系

論文名稱

Parallel Jacobi-Davidson Algorithms and Software Developments for Polynomial Eigenvalue Problems in Quantum Dot Simulation
(Parallel Jacobi-Davidson Algorithms and Software Developments for Polynomial Eigenvalue Problems in Quantum Dot Simulation )

相關論文

★ 非線性塊狀高斯消去牛頓演算法在噴嘴流體的應用	★ 以平行 Newton-Krylov-Schwarz 演算法解 Poisson-Boltzmann 方程式的有限元素解在膠體科學上的應用
★ 最小平方有限元素法求解對流擴散方程以及使用Bubble函數的改良	★ Bifurcation Analysis of Incompressible Sudden Expansion Flows Using Parallel Computing
★ An Inexact Newton Method for Drift-DiffusionModel in Semiconductor Device Simulations	★ Numerical Simulation of Three-dimensional Blood Flows in Arteries Using Domain Decomposition Based Scientific Software Packages in Parallel Computers
★ A Parallel Fully Coupled Implicit Domain Decomposition Method for the Stabilized Finite Element Solution of Three-dimensional Unsteady Incompressible Navier-Stokes Equations	★ A Study for Linear Stability Analysis of Incompressible Flows on Parallel Computers
★ Parallel Computation of Acoustic Eigenvalue Problems Using a Polynomial Jacobi-Davidson Method	★ Numerical Study of Algebraic Multigrid Methods for Solving Linear/Nonlinear Elliptic Problems on Sequential and Parallel Computers
★ A Parallel Multilevel Semi-implicit Scheme of Fluid Modeling for Numerical Low-Temperature Plasma Simulation	★ Performance Comparison of Two PETSc-based Eigensolvers for Quadratic PDE Problems
★ A Parallel Two-level Polynomial Jacobi-Davidson Algorithm for Large Sparse Dissipative Acoustic Eigenvalue Problems	★ A Full Space Lagrange-Newton-Krylov Algorithm for Minimum Time Trajectory Optimization
★ Parallel Two-level Patient-specific Numerical Simulation of Three-dimensional Rheological Blood Flows in Branching Arteries	★ A Markov Chain Multi-elimination Preconditioner for Elliptic PDE Problems on GPU

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

Jacobi-Davidson (JD) 演算法是一個解特徵值問題的迭代法，這些特徵值問題可以從一些工程或科學應用上的偏微分方程離散化所得來。在這篇論文中，我們針對量子點所產生的多項式特徵值問題求解。目前已有一些發展良好的平行套件，但是這些套件僅適合解決一般標準特徵值問題和廣義特徵值。所以我們利用 Portable, Extensible Toolkit for Scientific Computation (PETSc) 與 Scalable Library for Eigenvalue Problem Computations (SLEPc) 發展一個以 JD 為基礎的平行多用途科學計算軟體套件去解決多項式特徵值問題。JD 演算法是一種子空間法 (spbspace method)。在每次 JD 迭代，我們會利用 Rayleigh-Ritz procedure 從一個給定的 search space 去提取近似 Ritz-pair。如果近似的 Ritz-pair 不夠好，我們便需要透過解一個線性系統 correction equation 去增加一個基底向量到 search space。在 JD 演算法中，解 correction equation 是最 JD 演算法中昂貴的部份。所以對於迭代法去設計一個有效率的 preconditioner 是相當重要的。因此，我們提出並且研究 Schwarz 架構下的平行區域分割 preconditioner，這種 preconditioner 已被熟知並且廣泛利用在線性系統的求解，然而卻很少應用在特徵值問題上的研究。我們從五次與三次特徵值問題得到的數值結果顯示，在配合一些 Krylov 子空間法時，這樣的 preconditioner 是有效率並且能夠改進整體的 JD 收斂速率，進而在數百個處理器的平行電腦上得到相當卓越的效能。

摘要(英)

Jacobi-Davidson (JD) algorithm is one of the most popular iterative method for solving large sparse eigenvalue problems (EVPs) obtained from the discretization of some partial differential equations in many engineering and scientific applications. In this thesis, we target polynomial EVPs solved by the JD algorithm arising in quantum dot simulations. Although several existing state-of-the-art parallel packages, they are only suitable for solving standard or generalized EVPs. Therefore, we are developing a parallel general-purpose scientific software package based on JD method for solving polynomial EVPs using two powerful scientific software libraries, namely Portable, Extensible Toolkit for Scientific Computation (PETSc) and Scalable Library for Eigenvalue Problem Computations (SLEPc). JD algorithm is a class of subspace methods. At each JD iteration, an approximate eigenpair is extracted from a given search space through the Rayleigh-Ritz procedure. If the approximate eigenpair is not good enough, one needs to enlarge the search space by adding a new basis vector, which is obtained by solving a large sparse linear system, known as the correction equations. In the JD algorithm, solving the correction equation is the most expensive part. Therefore, to design an efficient preconditioner for some iterative method becomes very crucial. Hence, we proposed and studied a parallel domain-decomposed preconditioner based on the Schwarz framework, which is wildly used and well-understood for solving linear systems, but less studied for solving EVPs. Our numerical results obtaining from quintic and cubic EVPs show that such efficient preconditioner in conjunction with some Krylov subspace method, such as GMRES, can improve the overall convergence rate of the JD algorithm so that exhibit superior performance on a parallel machine up to few hundred processors.

關鍵字(中)

關鍵字(英)

★ polynomial eigenvalue problem
★ Jacobi-Davidson
★ quantum dot
★ parallel computing

論文目次

Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Parallel Jacobi-Davidson method for polynomial EVPs . . . . . . . . . . . . . . . . . 5
2.1 Jacobi-Davidson method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Brief introductions to PETSc and SLEPc . . . . . . . . . . . . . . . . . . . . . 8
2.3 Detailed parallel implementations using PETSc and SLEPc . . . . . . . . . . . . 9
3 Schr‥odinger equation and its discretization . . . . . . . . . . . . . . . . . . . . 14
3.1 Quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Quantum dots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Schr‥odinger equation and QD EVPs . . . . . . . . . . . . . . . . . . . . . . . 15
4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1 Parallel code validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Parametric study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 Effect of the inner JD stopping strategies . . . . . . . . . . . . . . . . . 24
4.2.2 Effect of quality of subdomain solve and overlapping size of RAS . . . . . 24
4.2.3 Scalability with respect to the number of processors and the problem sizes . 25
4.3 Parallel performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4 A large scale test problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
PJDPack user guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

參考文獻

[1] N. Alleborn, K. Nandakumar, H. Raszillier, and F. Durst. Further contributions on the two-dimensional flow in a sudden expansion. J. Fluid Mech., 330:169–188, 1997.
[2] P. Arbenz, M. Beˇcka, R. Geus, U. Hetmaniuk, and T. Mengotti. On a parallel multilevel preconditioned Maxwell eigensolver. Parallel Computing, 32(2):157–165, 2006.
[3] W. E. Arnoldi. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quart. Appl. Math., 9(17):17–29, 1951.
[4] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H.A. van der Vorst. Templates for the solution of algebraic eigenvalue problems: A practical guide. SIAM, 2000.
[5] S. Balay, K. Buschelman, V. Eijkhout, W.D. Gropp, D. Kaushik, M.G. Knepley, L.C. McInnes, B.F. Smith, and H. Zhang. PETSc users manual. Technical Report ANL-95/11 - Revision 2.1.5, Argonne National Laboratory, 2004.
[6] G. Bastard. Wave mechanics applied to semiconductor heterostructures. JohnWiley and Sons, New York, 1991.
[7] L. Bergamaschi, A. Martinez, G. Pini, and F. Sartoretto. Eigenanalysis of finite element 3D flow models by parallel Jacobi-Davidson. Lect Notes Comput Sci, pages 565–569, 2003.
[8] L. Bergamaschi, G. Pini, and F. Sartoretto. Computational experience with sequential and parallel, preconditioned Jacobi-Davidson for large, sparse symmetric matrices. J. Comput. Phys., 188(1):318–331, 2003.
[9] M. Bollhofer and Y. Notay. JADAMILU: a software code for computing selected eigenvalues of large sparse symmetric matrices. Comput. Phys. Commun., 177:951–964, December 2007.
[10] A. Booten, D. Fokkema, G. Sleijpen, and H.A. van der Vorst. Jacobi-Davidson methods for generalized MHD-eigenvalue problems. ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 76:131–134, 1996.
[11] J.G.L. Booten, H.A. van der Vorst, P.M. Meijer, and H.J.J. te Riele. A Preconditioned Jacobi-Davidson Method for Solving Large Generalized Eigenvalue Problems. Centrum voor Wiskunde en Informatica, 1994.
[12] K.-W. Eric Chu, T.-M. Hwang, W.-W. Lin, and C.-T. Wu. Vibration of fast trains, palindromic eigenvalue problems and structure-preserving doubling algorithms. J. Comput. Appl. Math., 219(1):237–252, 2008.
[13] S.L. Chuang, N. Peyghambarian, and S. Koch. Physics of optoelectronic devices, volume 49. Wiley, New York, American Institute of Physics, 1996.
[14] E. R. Davidson. The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real symmetric matrices. J. Comput. Phys., 17:87–94, 1975.
[15] D. R. Fokkema, G. L. G. Sleijpen, and H. A. Van der. Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils. SIAM J. Sci. Comput., 20(1):94–125, 1998.
[16] M. B. Van Gijzen. The parallel computation of the smallest eigenpair of an acoustic problem with damping. Int. J. Numer. Meth. Engng, 45:765–777, 1999.
[17] J. P. Goedbloed, S. Poedts, G. T. A. Huysmans, G. Halberstadt, H. Holties, and A. J. C. Beli‥en. Magnetohydrodynamic spectroscopy: Large scale computation of the spectrum of waves in plasmas. Future Gener. Comput. Syst., 10(2-3):339–343, 1994.
[18] P.M. Gresho, D.K. Gartling, J.R. Torczynski, K.A. Cliffe, K.H. Winters, T.J. Garratt, A. Spence, and J.W. Goodrich. Is the steady viscous incompressible twodimensional flow over a backward-facing step at Re= 800 stable? Internat. J. Numer. Methods Fluids, 17:501–541, 1993.
[19] J.-S. Guo, W.-W. Lin, and C.-S. Wang. Numerical solutions for large sparse quadratic eigenvalue problems. Linear Algebra Appl., 225:57–89, 1995.
[20] V. Hernandez, J.E. Roman, A. Tomas, and V. Vidal. SLEPc home page. http://www.grycap.upv.es/slepc, 2006.
[21] V. Hernandez, J.E. Roman, A. Tomas, and V. Vidal. SLEPc users manual. Technical Report DSIC-II/24/02 - Revision 2.3.2, D. Sistemas Inform′aticos y Computaci′on, Universidad Polit′ecnica de Valencia, 2006.
[22] V. Hernandez, J.E. Roman, and V. Vidal. SLEPc: Scalable Library for Eigenvalue Problem Computations. Lect Notes Comput Sci, 2565:377–391, 2003.
[23] V. Hernandez, J.E. Roman, and V. Vidal. SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems. ACM Transactions on Mathematical Software, 31(3):351–362, September 2005.
[24] T.-M. Hwang, W.-W. Lin, J.-L. Liu, and W. Wang. Jacobi-Davidson methods for cubic eigenvalue problems. Numer. Linear Algebra Appl, 12(7):605–624, 2005.
[25] T.-M. Hwang,W.-W. Lin,W.-C.Wang, andW.Wang. Numerical simulation of three dimensional pyramid quantum dot. J. Comput. Phys., 196(1):208–232, 2004.
[26] C.T. Kelley. Iterative methods for linear and nonlinear equations. SIAM, 1995.
[27] A.V. Knyazev. Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput, 23:517–541, 2001.
[28] R.B. Lehoucq and J.A. Scott. An evaluation of software for computing eigenvalues of sparse nonsymmetric matrices. Preprint MCS- P, 1195, 1996.
[29] Y. Li, O. Voskoboynikov, C.P. Lee, and S.M. Sze. Computer simulation of electron energy levels for different shape InAs/GaAs semiconductor quantum dots. Comput. Phys. Commun., 141(1):66–72, 2001.
[30] K. Meerbergen. Locking and restarting quadratic eigenvalue solvers. SIAM J. Sci. Comput., 22(5):1814–1839, 2001.
[31] M. Nool and A. van der Ploeg. Parallel Jacobi-Davidson for solving generalized eigenvalue problems. Lecture notes in computer science, pages 58–70, 1999.
[32] M. Nool and A. van der Ploeg. A parallel Jacobi-Davidson-type method for solving large generalized eigenvalue problems in magnetohydrodynamics. SIAM J. Sci. Comput., 22(1):95–112, 2000.
[33] Y. Notay. Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem. Numer. Linear Algebra Appl., 9(1):21–44, 2002.
[34] R.P. Pawlowski, A.G. Salinger, J.N. Shadid, and T.J. Mountziaris. Bifurcation and stability analysis of laminar isothermal counterflowing jets. J. Fluid Mech., 551:117–139, 2006.
[35] A. Quarteroni and A. Valli. Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, 1999.
[36] Y. Saad and M.H. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Comput., 7(3):856–869, 1986.
[37] J. Sanchez, F. Marques, and J.M. Lopez. A continuation and bifurcation technique for Navier-Stokes flows. J. Comput. Phys., 180(1):78–98, 2002.
[38] H.A. Schwarz. Gesammelte Mathematische Abhandlungen. Chelsea Publishing Company, June 1972.
[39] G.L.G. Sleijpen, A.G.L. Booten, D.R. Fokkema, and H.A. van der Vorst. Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems. BIT Numerical Mathematics, 36(3):595–633, 1996.
[40] G.L.G. Sleijpen and H.A. van der Vorst. A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl., 17:401–425, 1996.
[41] G.L.G. Sleijpen and H.A. van der Vorst. The Jacobi-Davidson method for eigenvalue problems and its relation with accelerated inexact Newton schemes. IMACS Ann. Comput. Appl. Math, 3:377–389, 1996.
[42] G.L.G. Sleijpen and H.A. van der Vorst. A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM Rev., 42(2):267–293, 2000.
[43] B.F. Smith, P.E. Bjørstad, and W. Gropp. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, 1996.
[44] A. Stathopoulos. Nearly optimal preconditioned methods for hermitian eigenproblems under limited memory. Part I: Seeking one eigenvalue. SIAM J. Sci. Comput., 29(2):481–514, 2007.
[45] A. Stathopoulos and J.R. McCombs. Nearly optimal preconditioned methods for hermitian eigenproblems under limited memory. Part II: Seeking many eigenvalues. SIAM J. Sci. Comput., 29(5):2162–2188, 2007.
[46] G. W. Stewart. A Krylov-Schur algorithm for large eigenproblems. Institute for Advanced Computer Studies TR, page 21, 2000.
[47] F. Tisseur. Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl., 309:339–361, 2000.
[48] F. Tisseur, K. Meerbergen, and Manchester Centre for Computational Mathematics. The quadratic eigenvalue problem. SIAM Rev., 43(2):235–286, 2001.
[49] A. Toselli and O.B.Widlund. Domain Decomposition Methods-Algorithms and Theory. Springer, 2005.
[50] H. Voss. A Jacobi-Davidson method for nonlinear and nonsymmetric eigenproblems. Comput. & Structures, 85(17-18):1284–1292, 2007.
[51] W.Wang, T.-M. Hwang,W.-W. Lin, and J.-L. Liu. Numerical methods for semiconductor heterostructures with band nonparabolicity. J. Comput. Phys., 190(1):141–158, 2003.
[52] K.Wu and H. Simon. Thick-restart Lanczos method for large symmetric eigenvalue problems. SIAM J. Matrix Anal. Appl., 22:602–616, 2001.

指導教授

黃楓南(Feng-Nan Hwang)

審核日期

2009-6-19

推文