In this thesis, we mainly study preconditioning techniques for all-at-once linear systems arising from discretization of three types of time-dependent advection-diffusion equation: linear diffusion equation, constant-coefficients advection-diffusion equation, time-fractional sub-diffusion equation. The proposed preconditioners are used with Krylov subspace solvers. The preconditioner developed for linear diffusion equation is based on -circulant ap- proximation of temporal discretization. Diagonalizability, clustering of spectrum and identity-plus-low-rank decomposition are derived for the preconditioned matrix. We also show that generalized minimal residual (GMRES) solver for the preconditioned system has a linear convergence rate independent of matrix-size. The preconditioner for constant-coefficients advection-diffusion equation is based on approximating the discretization of advection term with a matrix diagonalizable by sine transform. Eigenvalues of the preconditioned matrix are proven to be lower and upper bounded by positive constants independent of discretization parameters. Moreover, as the preconditioner is based on spatial approximation, it is also applicable to steady-state problem. We show that GMRES for the preconditioned steady-state problem has a linear convergence rate independent of matrix size. The preconditioner for time-fractional sub-diffusion equation is based on approximat- ing the discretization of diffusion term with a matrix diagonalizable by sine transform. We show that the condition number of the preconditioned matrix is bounded by a constant independent of discretization parameters so that the normalized conjugate gradient (NCG) solver for the preconditioned system has a linear convergence rate independent of discretization parameters and matrix size. Fast implementations based on fast Fourier transform (FFT), fast sine transform (FST) or multigrid approximation are proposed for the developed preconditioners. Numerical results are reported to show the performance of the developed preconditioners

published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

by Tat-Ming Tso. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (p. 43-45). / Chapter Chapter 1 --- INTRODUCTION --- p.1 / Chapter §1.1 --- Introduction --- p.1 / Chapter §1.2 --- Preconditioned Conjugate Gradient Method --- p.3 / Chapter §1.3 --- Outline of Thesis --- p.3 / Chapter Chapter 2 --- CIRCULANT AND NON-CIRCULANT PRECONDITIONERS --- p.5 / Chapter §2.1 --- Circulant Matrix --- p.5 / Chapter §2.2 --- Circulant Preconditioners --- p.6 / Chapter §2.3 --- Circulant Preconditioners from Kernel Function --- p.8 / Chapter §2.4 --- Non-circulant Band-Toeplitz Preconditioners --- p.9 / Chapter Chapter 3 --- B-SPLINES --- p.11 / Chapter §3.1 --- Introduction --- p.11 / Chapter §3.2 --- New Version of B-splines --- p.15 / Chapter Chapter 4 --- CIRCULANT PRECONDITIONERS CONSTRUCTED FROM B-SPLINES --- p.24 / Chapter Chapter 5 --- NUMERICAL RESULTS AND CONCLUDING REMARKS --- p.28 / Chapter Chapter 6 --- APPLICATIONS TO SIGNAL PROCESSING --- p.37 / Chapter §6.1 --- Introduction --- p.37 / Chapter §6.2 --- Preconditioned regularized least squares --- p.39 / Chapter §6.3 --- Numerical Example --- p.40 / REFERENCES --- p.43

by Joseph E. Wall, Jr., Alan S. Willsky, Nils R. Sandell, Jr. / Bibliography: leaf [27] / Department of Energy Contract ERDA-E-(49-18)-2087

University of Macau / Faculty of Science and Technology / Department of Mathematics

Thesis (Ph. D.)--University of Hong Kong, 1993.

Eigenstructure based techniques have been studied extensively in the last decade to estimate the number and locations of incoming radiating sources using a passive sensor array. One of the early limitations was the computational load involved in arriving at the eigendecompositions. The introduction of VLSI circuits and parallel processors however, has reduced the cost of computation A tremendously. As a consequence, we study eigendecomposition algorithms with highly parallel and A localized data flow, in order to take advantage of VLSI capabilities. This dissertation presents a fast Recursive/Iterative Toeplitz (Hermitian) Eigenspace (RITE) algorithm, and its extension to the generalized strongly regular eigendecomposition situation (C-RITE). Both procedures exhibit highly parallel structures, and their applicability to fast passive array processing is emphasized. The algorithms compute recursively in increasing order, the complete (generalized) eigendecompositions of the successive subproblems contained in the maximum size one. At each order, a number of independent, structurally identical, non-linear problems is solved in parallel. The (generalized) eigenvalues are found by quadratically convergent iterative search techniques. Two different search methods, a restricted Newton approach and a rational approximation based technique are considered. The eigenvectors are found by solving Toeplitz systems efficiently. The multiple minimum (generalized) eigenvalue case and the case of a cluster of small (generalized) eigenvalues are treated also. Eigenpair residual norms and orthonormality norms in comparison with IMSL library routines, indicate good performance and stability behavior for increasing dimensions for both the RITE and C-RITE algorithms. Application of the procedures to the Direction Of Arrival (DOA) identification problem, using the MUSIC algorithm, is presented. The order-recursive properties of RITE and C-RITE permit estimation of angles for all intermediate orders imbedded in the original problem, facilitating the earliest possible estimation of the number and location of radiating sources. The detection algorithm based on RITE or C-RITE can then stop, thereby minimizing the overall computational load to that corresponding to the smallest order for which angle of arrival estimation is indicated to be reliable. Some extensions of the RITE procedure to Hermitian (non-Toeplitz) matrices are presented. This corresponds in the array processing context to correlation matrices estimated from non-linear arrays or incoming signals with non-stationary characteristics. A first—order perturbation approach and two Subspace Iteration (SI) methods are investigated. The RITE decomposition of the Toeplitzsized (diagonally averaged) matrix is used as a starting point. Results show that the SI based techniques lead to good approximation of the eigen-information, with the rate of convergence depending upon the SNR ar1d the angle difference between incoming sources, the convergence being faster than starting the SI method from an arbitrary initial matrix. / Ph. D.

[pt] Em 1994, Henry Landau mostrou que uma matriz de Toeplitz real simétrica pode assumir qualquer valor real. O objetivo desse texto é apresentar a demonstração de Landau. São empregadas técnicas de teoria de grau topológico e teoria espectral. / [en] In 1994, Henry Landau proved that a real, symmetric Toeplitz matrix obtains an arbitrary real spectrum. In this text, we present the details of his proof. The key ingredients are topological degree theory and spectral theory.

Kwok-po Ng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 138-139). / Abstracts / Summary / Introduction --- p.1 / Summary of the papers A-F --- p.2 / Paper A --- p.15 / Paper B --- p.36 / Paper C --- p.63 / Paper D --- p.87 / Paper E --- p.109 / Paper F --- p.122

by Wun-Cheung Tang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references. / Abstract also in Chinese. / Abstracts --- p.1 / Introduction --- p.3 / Toeplitz and Circulant Matrices --- p.3 / Conjugate Gradient Method --- p.6 / Cosine Transform Preconditioner --- p.7 / Regularization --- p.10 / Summary --- p.13 / Paper A --- p.19 / Paper B --- p.36