Fast Mixed Precision Algorithms for Toeplitz Least Squares Problems Open Access

Abstract

This thesis presents a fast mixed precision algorithm to solve least squares problems min ||Ax-b||^2_2+alpha^2||x||^2_2 when A is a Teoplitz matrix (alpha could be zero for general problems), which arise in many applications like signal deblurring. This algorithm utilizes the special structure of the Toeplitz matrix to construct the Cholesky factorization of matrix A'A in lower precision to solve for x and executes GMRES iterative refinement in higher precision to improve the accuracy of the solution. It is found that the precision used for the computation of the Cholesky factorization does not affect the accuracy of the result in cases when b is corrupted by noise. Using double precision in both refinement and calculating the residual is the most efficient, requiring only 1 refinement iteration. However, using single precision for refinement and double for calculating the residual can reach the same level of accuracy with one or two refinement iteration(s).

Table of Contents

1 Introduction 1

2 Deconvolution 4

3 Least Squares Problems 10

3.1 Methods to solve least squares problems 10

3.2 Rank-1 updating 13

3.3 Rank-1 downdating 15

3.4 Iterative refinement 18

4 Approaches for Toeplitz Systems 20

4.1 The Cholesky factorization for Toeplitz least squares problem 20

4.2 The Cholesky factorization for regularized Toeplitz least squares problem 23

4.3 The inverse Cholesky factorization for Toeplitz least squares problem 24

4.4 Refinement for regularized Toeplitz least squares problem with preconditioner 28

5 Numerical Experiments 32

6 Concluding Remarks 38

Bibliography 40

About this Honors Thesis

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Mathematics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Mathematics
Keyword	Toeplitz Matrix Iterative Refinement Least Squares Problems Mixed Precision
Committee Chair / Thesis Advisor	James Nagy, Emory University
Committee Members	Michael Rogers, Emory University Julianne Chung, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Fast Mixed Precision Algorithms for Toeplitz Least Squares Problems ()	2024-04-05 21:53:55 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions