Projection Methods in IDR - Overview & Application Insights
Discover the essence of IDR as a projection method through iterative methods, projection methods, Krylov subspace methods, and more. Uncover the analytical frameworks behind finding approximate solutions, defining subspaces, and selecting algorithms for optimal results.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
IDR(?) as a projection method Marijn Bartel Schreuders Supervisor: Dr. Ir. M.B. Van Gijzen Date: Monday, 24 February 2014 1 IDR(?) as a projection method
Overview of this presentation Iterative methods Projection methods Krylov subspace methods Eigenvalue problems Linear systems of equations The IDR(?) method General idea behind the IDR(?) method Numerical examples Ritz-IDR Research Goals 2 IDR(?) as a projection method
Iterative methods Consider a linear system ?? = ? (1) with ? ? ?and ? ? Find an approximate solution ?? to (1), with initial guess ?0 Residual ??= ? ??? 3 IDR(?) as a projection method
Projection methods Subspaces Define ?? ? ?of dimension ? ? Subspace of candidate approximants or Search subspace Define ? ? ?of dimension ? ? Subspace of constraints or Left subspace 4 IDR(?) as a projection method
Projection methods Definition Find ?? ?0+ ?? such that ?? ? Find ?? ?0+ ?? Let ??= ?1,?2, ,?? form an orthonormal basis for ?? Then ??= ?0+ ?=1 ? ??,??? = ?0+ ???? How to find this vector? 5 IDR(?) as a projection method
Projection methods How to find ?? Let Wm= ?1,?2, ,?? form an orthonormal basis for ? ??= ? ??? = ? ? ?0+ ???? = ?0 ????? ???= 0 ?? 1Wm ??0= (?? ????)?? TAVm Tr0 Hence: ?? ym= Wm ??= ?0+ ???? 6 IDR(?) as a projection method
Projection methods General algorithm How to choose the subspaces? 7 IDR(?) as a projection method
Krylov subspace methods General ???,?1 = ???? ?1, ??1, ?2?1, , ?? 1?1 Different methods for different choices of ? Can be used for eigenvalue problems linear systems of equations 8 IDR(?) as a projection method
Krylov subspace methods Overview 9 IDR(?) as a projection method
Krylov subspace methods Overview 10 IDR(?) as a projection method
Krylov subspace methods Eigenvalue problems Computing all eigenvalues can be costly A is a full matrix A is large Idea: find smaller matrix for which it is easy to compute Ritz values Good approximations to some of the eigenvalues of A 11 IDR(?) as a projection method
Krylov subspace methods Overview 12 IDR(?) as a projection method
Krylov subspace methods Overview 13 IDR(?) as a projection method
Krylov subspace methods Symmetric matrices Conjugate Gradient method (CG) Optimality condition Uses short recurrences Minimises the residual 14 IDR(?) as a projection method
Krylov subspace methods Nonsymmetric matrices GMRES-type methods Long recurrences Minimisation of the residual Bi-CG type methods Short recurrences No minimisation of the residual Two matrix-vector operations per iteration Are their any other possibilities? 15 IDR(?) as a projection method
Induced Dimension Reduction (s) Residuals are forced to be in certain subspaces Compute ? residuals in each iteration 16 IDR(?) as a projection method
Induced Dimension Reduction (s) IDR theorem Theorem 1 (IDR theorem): Let ? ? ? and ?0 ? Let ?0= ???,?0 Let ? ? such that ? and ?0do not share a subspace of ? Define: ??= (? ???)(?? 1 ?) Then the following holds: (i) (ii) ??+1 ?? ? 0 ??= {0} for some ? < ? 17 IDR(?) as a projection method
Induced Dimension Reduction (s) Numerical experiments Convection diffusion equation: ? ? = ? + ??? Discretise using finite differences on unit cube; Dirichlet boundary conditions 20internal points 8000 equations Stopping criterion: < ? 10 8 ?? 18 IDR(?) as a projection method
Induced Dimension Reduction (s) Numerical experiments This is an example of a slide 19 IDR(?) as a projection method
Induced Dimension Reduction (s) Numerical experiments Matrix Market: ???20 matrix Real, nonsymmetric, sparse 2395 2395 matrix http://math.nist.gov/MatrixMarket/data/misc/hamm/add20.html http://math.nist.gov/MatrixMarket/data/misc/hamm/add20.html 20 IDR(?) as a projection method
Induced Dimension Reduction (s) Numerical experiments This is an example of a slide 21 IDR(?) as a projection method
Induced Dimension Reduction (s) Numerical experiments This is an example of a slide 22 IDR(?) as a projection method
Induced Dimension Reduction (s) How to choose ?? Recall: ??= (? ???)(?? 1 ?) How to choose ??? Minimisation of the residuals Random? ? 23 IDR(?) as a projection method
Induced Dimension Reduction (s) Ritz-IDR Valeria Simoncini & Daniel Szyld Ritz-IDR Calculates Ritz values ?? 1 ?? ??= 24 IDR(?) as a projection method
Research goals Research goals are twofold: 1. Make clear how we can see IDR(?) in the framework of projection methods 2. Use the IDR(s) algorithm for calculating the ?? ? 25 IDR(?) as a projection method
IDR(?) as a projection method Marijn Bartel Schreuders Supervisor: Dr. Ir. M.B. Van Gijzen Date: Monday, 24 February 2014 26 IDR(?) as a projection method
27 IDR(?) as a projection method
Research goals ?? = ?? ????? Let ???= ?? = ?? ???? ??? ???? = ?? ???? ??? 2?? ??? 2???? ???+ ?? = ?? This is a polynomial in ?? To minimise, take derivative w.r.t. ?? 28 IDR(?) as a projection method
Krylov subspace methods Eigenvalue problems Arnoldi Method Lanczos method & Bi-Lanczos method 29 IDR(?) as a projection method
