자료유형  

 학위논문

Control Number  

0016934417

International Standard Book Number  

9798380276368

Dewey Decimal Classification Number  

300

Main Entry-Personal Name  

Gnanasekaran, Abeynaya.

Publication, Distribution, etc. (Imprint  

[S.l.] : Stanford University., 2022

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2022

Physical Description  

1 online resource(172 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

General Note  

Advisor: Alonso, Juan Jose;Gerritsen, Margot.

Dissertation Note  

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

Restrictions on Access Note  

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

Summary, Etc.  

요약Sparse linear systems and least-squares problems appear in various scientific applications ranging from classic domains like computational physics to growing fields like data science. In many of these applications, solving these systems are often the most expensive step. In this thesis, we discuss the development, application and a parallel implementation of a novel, fast, approximate QR factorization that can be used to solve general sparse linear systems and least-squares problems. This is organized into three parts as follows.In the first part (chapters 2 and 3), we discuss the development of our novel fast QR factorization, sparsified QR (spaQR). spaQR is a fast hierarchical solver that is built on the ideas of nested dissection, Householder QR and low-rank compressions. By using a two-step compression scheme, spaQR reduces the size of the nested dissection separators while approximately preserving the original structure of the elimination tree. A small approximation error is introduced which can be controlled by the user. We show that spaQR computes the factorization in near linear time and takes linear time to solve with a vector.In the second part, we focus on the application of spaQR for solving a wide variety of matrices arising from real applications. We demonstrate that spaQR exhibits near-linear scalings and is an ecient preconditioner for sparse linear systems arising in CFD applications (covered in chapter 2) and least-squares problems arising in PDE constrained optimization problems (covered in chapter 3). In chapter 4, we study the performance of spaQR on three di↵erent problems that arise in computer graphics - laplacian mesh reconstruction, conformal mapping and as-rigid-as-possible deformation. High performance is crucial here for interactive user feedback and approximate solutions often work well enough. We demonstrate that spaQR is faster than the standard techniques for these problems and hence can be an asset to these applications.In the third part (chapters 5 and 6), we develop a new task-based distributed memory implementation of spaQR using the TaskTorrent runtime system. We study the strong scaling behavior of our solver on a few large linear systems and least-squares problems on up to 1024 cores. We show that spaQR scales well for moderately sized 3D problems. The rank revealing QR factorization (RRQR), which is used to provide the low-rank approximations acts a bottleneck on larger problems. In chapter 6, we present a new parallel task-based algorithm for randomized low-rank factorizations of a matrix. We present a set of benchmarks comparing our implementation with similar implementations in state-of-art platforms like StarPU, PaRSEC and ScaLAPACK. Finally, we incorporate the randomized low-rank factorization in place of the RRQR and demonstrate that it improves the scalability of spaQR for large 3D problems.Another major contribution of my work is to provide open-source implementations of the sequential and parallel spaQR code.

Subject Added Entry-Topical Term  

Internships.

Subject Added Entry-Topical Term  

Reynolds number.

Subject Added Entry-Topical Term  

Dissection.

Subject Added Entry-Topical Term  

Linear algebra.

Subject Added Entry-Topical Term  

Interfaces.

Subject Added Entry-Topical Term  

Benchmarks.

Subject Added Entry-Topical Term  

Fluid mechanics.

Subject Added Entry-Topical Term  

Mathematics.

Subject Added Entry-Topical Term  

Mechanics.

Added Entry-Corporate Name  

Stanford University.

Host Item Entry  

Dissertations Abstracts International. 85-03B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:642068