Multiple-rank updates to matrix factorizations for nonlinear analysis and circuit design
Abstract/Contents
- Abstract
- For the numerical solution of ODE/PDEs that describe the basic laws of science, such as Kirchhoff's laws in circuit analysis, or nonlinear deformation equations in structural analysis, a series of linear equations Ax=b are generated to represent the basic laws. The size of A could reach 10 billion in full-chip verification, or 1 billion in structure-foundation seismic simulation. The traditional method is to solve these linear equations independently, which leads to a computational bottleneck when we simulate large and complicated objects because more than 95 percent of the simulation time lies in solving the equations. This thesis addresses the computational bottleneck by modifying the matrix A's factorization at each simulation step based on the similarities between two consecutive linear systems. To achieve this aim, we define the similarities as an initial matrix A with multiple-rank corrections. Then we design algorithms to solve the linear systems based on updating concepts. The basic algorithm is a rank-1 update of the factors of an unsymmetric matrix. To maintain stability, new algorithms are designed to implement partial or full pivoting strategies for the update procedure. To improve performance and overcome parallelization difficulties during traditional factorization, a pipeline is designed to do multiple-rank updates of the matrix factors. We prove two theorems for this parallel computing. One states that the multiple-rank update sequences are independent. The other, called the Base-camp theorem, describes a multiple-rank merge rule to reduce the computing effort. A divide-and-conquer algorithm for sparse matrix factorization is also described. Finally, we apply the multiple-rank modification of matrix factors to nonlinear analysis in structural engineering and functionality verification in circuit design. The same process can be applied in other time-domain problems and nonlinear systems, including fluid dynamics, aerospace, chemical processing, structure analysis, graphics rendering, MEMS, seismic, biotech, and electromagnetic field analyses.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Deng, Linzhong |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Saunders, Michael A |
| Thesis advisor | Saunders, Michael A |
| Thesis advisor | Liu, Zhihong, (Computational engineer) |
| Thesis advisor | Murray, Walter |
| Advisor | Liu, Zhihong, (Computational engineer) |
| Advisor | Murray, Walter |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Linzhong Deng. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph. D.)--Stanford University, 2010. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2010 by Linzhong Deng
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...