東華大學圖書館 |

Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning./
作者:	Faba, Jordi Feliu.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
面頁冊數:	175 p.
附註:	Source: Dissertations Abstracts International, Volume: 83-09, Section: B.
Contained By:	Dissertations Abstracts International83-09B.
標題:	Sparsity. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28971822
ISBN:	9798780652830

Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning.
Faba, Jordi Feliu.

Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 175 p.

Source: Dissertations Abstracts International, Volume: 83-09, Section: B.

Thesis (Ph.D.)--Stanford University, 2021.

This item must not be sold to any third party vendors.

This dissertation introduces fast factorizations for sparse and dense matrices, allowing to represent or invert pseudo-differential and Fourier integral operators. This thesis is organized in the following three main parts.In the first part (chapters 2 to 4) we develop fast and robust hierarchical solvers for sparse matrices based on the hierarchical interpolative factorization (HIF). HIF is a fast algorithm for approximate sparse matrix inversion in linear or quasi-linear time, that compresses fillins throughout the matrix factorization. Its accuracy can degrade, however, when applied to strongly ill-conditioned problems.In chapter 2 we introduce the recursively preconditioned interpolative factorization (PHIF) by adding a modification that can significantly improve the accuracy at no additional asymptotic cost: applying a block Jacobi preconditioner before each level of skeletonization. This dramatically limits the impact of the underlying system conditioning and enables the construction of robust and highly efficient preconditioners even at quite modest compression tolerances. When applied to symmetric positive definite (SPD) matrices, HIF can break due to the loss of positive definiteness for high compression tolerance. We prove that it is possible to modify the original algorithm to guarantee that the matrix always remains SPD. Numerical examples in 2D and 3D demonstrate its performance. Most state-of-the-art fast solvers for sparse matrices focus on the SPD case. In chapter 3 we develop a new strategy for factorizing unsymmetric matrices. We propose an algorithm with optimal unsymmetric compression of fill-ins and unsymmetric scaling of the off-diagonal blocks arising in the factorization. We demonstrate with numerical examples that this approach performs better.In chapter 4 we apply PHIF to parabolic equations, such as reaction diffusion equations. With the Crank-Nicholson time stepping method, the algebraic system of equations at each time step is solved with the conjugate gradient method, preconditioned with PHIF. Stiffness matrices arising in the discretization of parabolic equations typically have large condition numbers, and therefore preconditioning becomes essential, especially for large time steps.The second part (chapter 5) introduces a machine learning approach to parameterize pseudo-differential operators with deep neural networks. With the help of the nonstandard wavelet form, the pseudo-differential operators can be approximated in a compressed form with a collection of vectors. The nonlinear map from the parameter to this collection of vectors and the wavelet transform are learned together from a small number of matrix-vector multiplications of the pseudo-differential operator. Numerical results for Green's functions of elliptic partial differential equations and the radiative transfer equations demonstrate the efficiency and accuracy of the proposed approach.The third part (chapter 6) introduces a factorization for the inverse of discrete Fourier integral operators of size N x N that can be applied in quasi-linear time. The factorization starts by approximating the operator with the butterfly factorization. Next, a hierarchical matrix representation is constructed for the hermitian matrix arising from composing the Fourier integral operator with its adjoint. This representation is inverted efficiently with a new algorithm based on HIF. By combining these two factorizations, an approximate inverse factorization for the Fourier integral operator is obtained as a product of O(log N) sparse matrices with O(N) entries. The resulting approximate inverse factorization can be used as a direct solver or as a preconditioner. Numerical examples on 1D and 2D Fourier integral operators, including a generalized Radon transform, demonstrate the efficiency of the factorization.

ISBN: 9798780652830Subjects--Topical Terms:

3680690
Sparsity.

Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning.
LDR:04904nmm a2200325 4500 001 2349907
005 20221010063654.5
008 241004s2021 ||||||||||||||||| ||eng d
020 $a 9798780652830
035 $a (MiAaPQ)AAI28971822
035 $a (MiAaPQ)STANFORDxv565rm8453
035 $a AAI28971822
040 $a MiAaPQ $c MiAaPQ
100 1 $a Faba, Jordi Feliu. $3 3689333
245 1 0 $a Multiscale Algorithms for Structured Matrices: Fast Solvers and Deep Learning.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 175 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-09, Section: B.
500 $a Advisor: Ying, Lexing;Darve, Eric.
502 $a Thesis (Ph.D.)--Stanford University, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a This dissertation introduces fast factorizations for sparse and dense matrices, allowing to represent or invert pseudo-differential and Fourier integral operators. This thesis is organized in the following three main parts.In the first part (chapters 2 to 4) we develop fast and robust hierarchical solvers for sparse matrices based on the hierarchical interpolative factorization (HIF). HIF is a fast algorithm for approximate sparse matrix inversion in linear or quasi-linear time, that compresses fillins throughout the matrix factorization. Its accuracy can degrade, however, when applied to strongly ill-conditioned problems.In chapter 2 we introduce the recursively preconditioned interpolative factorization (PHIF) by adding a modification that can significantly improve the accuracy at no additional asymptotic cost: applying a block Jacobi preconditioner before each level of skeletonization. This dramatically limits the impact of the underlying system conditioning and enables the construction of robust and highly efficient preconditioners even at quite modest compression tolerances. When applied to symmetric positive definite (SPD) matrices, HIF can break due to the loss of positive definiteness for high compression tolerance. We prove that it is possible to modify the original algorithm to guarantee that the matrix always remains SPD. Numerical examples in 2D and 3D demonstrate its performance. Most state-of-the-art fast solvers for sparse matrices focus on the SPD case. In chapter 3 we develop a new strategy for factorizing unsymmetric matrices. We propose an algorithm with optimal unsymmetric compression of fill-ins and unsymmetric scaling of the off-diagonal blocks arising in the factorization. We demonstrate with numerical examples that this approach performs better.In chapter 4 we apply PHIF to parabolic equations, such as reaction diffusion equations. With the Crank-Nicholson time stepping method, the algebraic system of equations at each time step is solved with the conjugate gradient method, preconditioned with PHIF. Stiffness matrices arising in the discretization of parabolic equations typically have large condition numbers, and therefore preconditioning becomes essential, especially for large time steps.The second part (chapter 5) introduces a machine learning approach to parameterize pseudo-differential operators with deep neural networks. With the help of the nonstandard wavelet form, the pseudo-differential operators can be approximated in a compressed form with a collection of vectors. The nonlinear map from the parameter to this collection of vectors and the wavelet transform are learned together from a small number of matrix-vector multiplications of the pseudo-differential operator. Numerical results for Green's functions of elliptic partial differential equations and the radiative transfer equations demonstrate the efficiency and accuracy of the proposed approach.The third part (chapter 6) introduces a factorization for the inverse of discrete Fourier integral operators of size N x N that can be applied in quasi-linear time. The factorization starts by approximating the operator with the butterfly factorization. Next, a hierarchical matrix representation is constructed for the hermitian matrix arising from composing the Fourier integral operator with its adjoint. This representation is inverted efficiently with a new algorithm based on HIF. By combining these two factorizations, an approximate inverse factorization for the Fourier integral operator is obtained as a product of O(log N) sparse matrices with O(N) entries. The resulting approximate inverse factorization can be used as a direct solver or as a preconditioner. Numerical examples on 1D and 2D Fourier integral operators, including a generalized Radon transform, demonstrate the efficiency of the factorization.
590 $a School code: 0212.
650 4 $a Sparsity. $3 3680690
650 4 $a Partial differential equations. $3 2180177
650 4 $a Wavelet transforms. $3 3681479
650 4 $a Algorithms. $3 536374
650 4 $a Neural networks. $3 677449
650 4 $a Artificial intelligence. $3 516317
650 4 $a Computer science. $3 523869
650 4 $a Mathematics. $3 515831
690 $a 0800
690 $a 0984
690 $a 0405
710 2 $a Stanford University. $3 754827
773 0 $t Dissertations Abstracts International $g 83-09B.
790 $a 0212
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28971822