An official website of the United States government
Abstract It is known that the solutions to space‐fractional diffusion equations exhibit singularities near the boundary. Therefore, numerical methods discretized on the composite mesh, in which the mesh size is refined near the boundary, provide more precise approximations to the solutions. However, the coefficient matrices of the corresponding linear systems usually lose the diagonal dominance and are ill‐conditioned, which in turn affect the convergence behavior of the iteration methods.In this work we study a finite volume method for two‐sided fractional diffusion equations, in which a locally refined composite mesh is applied to capture the boundary singularities of the solutions. The diagonal blocks of the resulting three‐by‐three block linear system are proved to be positive‐definite, based on which we propose an efficient block Gauss–Seidel method by decomposing the whole system into three subsystems with those diagonal blocks as the coefficient matrices. To further accelerate the convergence speed of the iteration, we use T. Chan's circulant preconditioner31as the corresponding preconditioners and analyze the preconditioned matrices' spectra. Numerical experiments are presented to demonstrate the effectiveness and the efficiency of the proposed method and its strong potential in dealing with ill‐conditioned problems. While we have not proved the convergence of the method in theory, the numerical experiments show that the proposed method is convergent.
more »
« less
Preconditioning for accurate solutions of ill‐conditioned linear systems
Summary This article develops the preconditioning technique as a method to address the accuracy issue caused by ill‐conditioning. Given a preconditionerMfor an ill‐conditioned linear systemAx=b, we show that, if the inverse of the preconditionerM−1can be applied to vectorsaccurately, then the linear system can be solvedaccurately. A stability concept calledinverse‐equivalentaccuracy is introduced to describe the high accuracy that is achieved and an error analysis will be presented. Numerical examples are presented to illustrate the error analysis and the performance of the methods.
more »
« less
- Award ID(s):
- 1821144
- PAR ID:
- 10458312
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Numerical Linear Algebra with Applications
- Volume:
- 27
- Issue:
- 4
- ISSN:
- 1070-5325
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Discrete ill‐posed inverse problems arise in many areas of science and engineering. Their solutions are very sensitive to perturbations in the data. Regularization methods aim at reducing this sensitivity. This article considers an iterative regularization method, based on iterated Tikhonov regularization, that was proposed in M. Donatelli and M. Hanke, Fast nonstationary preconditioned iterative methods for ill‐posed problems, with application to image deblurring,Inverse Problems, 29 (2013), Art. 095008, 16 pages. In this method, the exact operator is approximated by an operator that is easier to work with. However, the convergence theory requires the approximating operator to be spectrally equivalent to the original operator. This condition is rarely satisfied in practice. Nevertheless, this iterative method determines accurate image restorations in many situations. We propose a modification of the iterative method, that relaxes the demand of spectral equivalence to a requirement that is easier to satisfy. We show that, although the modified method is not an iterative regularization method, it maintains one of the most important theoretical properties for this kind of methods, namely monotonic decrease of the reconstruction error. Several computed experiments show the good performances of the proposed method.more » « less
-
Summary In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus calledstructuredFISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.more » « less
-
Summary We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.more » « less
-
With the advent of massive data sets much of the computational science and engineering community has moved toward data-intensive approaches in regression and classification. However, these present significant challenges due to increasing size, complexity and dimensionality of the problems. In particular, covariance matrices in many cases are numerically unstable and linear algebra shows that often such matrices cannot be inverted accurately on a finite precision computer. A common ad hoc approach to stabilizing a matrix is application of a so-called nugget. However, this can change the model and introduce error to the original solution. It is well known from numerical analysis that ill-conditioned matrices cannot be accurately inverted. In this paper we develop a multilevel computational method that scales well with the number of observations and dimensions. A multilevel basis is constructed adapted to a kD-tree partitioning of the observations. Numerically unstable covariance matrices with large condition numbers can be transformed into well conditioned multilevel ones without compromising accuracy. Moreover, it is shown that the multilevel prediction exactly solves the Best Linear Unbiased Predictor (BLUP) and Generalized Least Squares (GLS) model, but is numerically stable. The multilevel method is tested on numerically unstable problems of up to 25 dimensions. Numerical results show speedups of up to 42,050 times for solving the BLUP problem, but with the same accuracy as the traditional iterative approach. For very ill-conditioned cases the speedup is infinite. In addition, decay estimates of the multilevel covariance matrices are derived based on high dimensional interpolation techniques from the field of numerical analysis. This work lies at the intersection of statistics, uncertainty quantification, high performance computing and computational applied mathematics.more » « less
