| Popis: |
In this dissertation, we study stable and efficient methods for structured matrix computations. In particular, we present stability analysis, stabilization strategies, and efficiency improvements for some major structured matrix algorithms. Structured matrix computations now play an important role in many applications. Compared to traditional algorithms, it can reduce significantly the algorithm complexity, by capturing and taking advantage of the intrinsic structures of the underlying problems. This dissertation overcomes some major challenges and presents some novel results in the design and analysis of structured matrix algorithms. These results have been previously overlooked due to the complex nature of the structured methods. We show how to integrate many stabilization techniques into efficient structured methods. The stability and efficiency of the resulting algorithms are justified both theoretically and numerically. In Chapter 2, we propose a stable matrix version of the fast multipole method (FMM) in the complex plane. The advantage of our stable FMM is that all the intermediate low-rank matrices will have bounded entries and bounded norms, so that they can be computed stably and efficiently. Based on this, we give a formal proof of the backward stability of our stable FMM. In Chapter 3, we propose a robust and superfast divide-and-conquer eigensolver (SuperDC) for symmetric structured matrices, which significantly improves some earlier basic algorithms. The complexity of SuperDC for getting the full eigenvalue decomposition is quasilinear, as compared to the cubic cost of traditional divide and conquer. Such acceleration is achieved by integrating our stable FMM in a novel but subtle way with the modified Newton-Raphson method for the solution of some intermediate rank-one modification eigenvalue problems. Numerical tests demonstrate its superior performance in terms of speed and memory. To accommodate more general problems, we also extend SuperDC to compute the singular value decomposition of nonsymmetric structured matrices. In Chapter 4, we consider the efficient factorization update for some shifted discretized matrices. After an $O(n)$ precomputation stage, the factorization update for each new shift needs only $O(\sqrt{n}\log n)$, which is significantly more efficient than doing refatorizations. The various contributions of this dissertation significantly advance the reliability, accuracy, and efficiency of structured matrix computations. |
