skip to main content

Title: Solution of ill-posed problems with Chebfun

The analysis of linear ill-posed problems often is carried out in function spaces using tools from functional analysis. However, the numerical solution of these problems typically is computed by first discretizing the problem and then applying tools from finite-dimensional linear algebra. The present paper explores the feasibility of applying the Chebfun package to solve ill-posed problems with a regularize-first approach numerically. This allows a user to work with functions instead of vectors and with integral operators instead of matrices. The solution process therefore is much closer to the analysis of ill-posed problems than standard linear algebra-based solution methods. Furthermore, the difficult process of explicitly choosing a suitable discretization is not required.

more » « less
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Numerical Algorithms
Page Range / eLocation ID:
p. 2341-2364
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    The reduction of a large‐scale symmetric linear discrete ill‐posed problem with multiple right‐hand sides to a smaller problem with a symmetric block tridiagonal matrix can easily be carried out by the application of a small number of steps of the symmetric block Lanczos method. We show that the subdiagonal blocks of the reduced problem converge to zero fairly rapidly with increasing block number. This quick convergence indicates that there is little advantage in expressing the solutions of discrete ill‐posed problems in terms of eigenvectors of the coefficient matrix when compared with using a basis of block Lanczos vectors, which are simpler and cheaper to compute. Similarly, for nonsymmetric linear discrete ill‐posed problems with multiple right‐hand sides, we show that the solution subspace defined by a few steps of the block Golub–Kahan bidiagonalization method usually can be applied instead of the solution subspace determined by the singular value decomposition of the coefficient matrix without significant, if any, reduction of the quality of the computed solution.

    more » « less
  2. 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
  3. Abstract

    The goal of this work is to predict the effect of part geometry and process parameters on the instantaneous spatial distribution of heat, called the heat flux or thermal history, in metal parts as they are being built layer-by-layer using additive manufacturing (AM) processes. In pursuit of this goal, the objective of this work is to develop and verify a graph theory-based approach for predicting the heat flux in metal AM parts. This objective is consequential to overcome the current poor process consistency and part quality in AM. One of the main reasons for poor part quality in metal AM processes is ascribed to the heat flux in the part. For instance, constrained heat flux because of ill-considered part design leads to defects, such as warping and thermal stress-induced cracking. Existing non-proprietary approaches to predict the heat flux in AM at the part-level predominantly use mesh-based finite element analyses that are computationally tortuous — the simulation of a few layers typically requires several hours, if not days. Hence, to alleviate these challenges in metal AM processes, there is a need for efficient computational thermal models to predict the heat flux, and thereby guide part design and selection of process parameters instead of expensive empirical testing. Compared to finite element analysis techniques, the proposed mesh-free graph theory-based approach facilitates layer-by-layer simulation of the heat flux within a few minutes on a desktop computer. To explore these assertions we conducted the following two studies: (1) comparing the heat diffusion trends predicted using the graph theory approach, with finite element analysis and analytical heat transfer calculations based on Green’s functions for an elementary cuboid geometry which is subjected to an impulse heat input in a certain part of its volume, and (2) simulating the layer-by-layer deposition of three part geometries in a laser powder bed fusion metal AM process with: (a) Goldak’s moving heat source finite element method, (b) the proposed graph theory approach, and (c) further comparing the heat flux predictions from the last two approaches with a commercial solution. From the first study we report that the heat flux trend approximated by the graph theory approach is found to be accurate within 5% of the Green’s functions-based analytical solution (in terms of the symmetric mean absolute percentage error). Results from the second study show that the heat flux trends predicted for the AM parts using graph theory approach agrees with finite element analysis with error less than 15%. More pertinently, the computational time for predicting the heat flux was significantly reduced with graph theory, for instance, in one of the AM case studies the time taken to predict the heat flux in a part was less than 3 minutes using the graph theory approach compared to over 3 hours with finite element analysis. While this paper is restricted to theoretical development and verification of the graph theory approach for heat flux prediction, our forthcoming research will focus on experimental validation through in-process sensor-based heat flux measurements.

    more » « less
  4. Inverse problems are ubiquitous in science and engineering. Two categories of inverse problems concerning a physical system are (1) estimate parameters in a model of the system from observed input–output pairs and (2) given a model of the system, reconstruct the input to it that caused some observed output. Applied inverse problems are challenging because a solution may (i) not exist, (ii) not be unique, or (iii) be sensitive to measurement noise contaminating the data. Bayesian statistical inversion (BSI) is an approach to tackle ill-posed and/or ill-conditioned inverse problems. Advantageously, BSI provides a “solution” that (i) quantifies uncertainty by assigning a probability to each possible value of the unknown parameter/input and (ii) incorporates prior information and beliefs about the parameter/input. Herein, we provide a tutorial of BSI for inverse problems by way of illustrative examples dealing with heat transfer from ambient air to a cold lime fruit. First, we use BSI to infer a parameter in a dynamic model of the lime temperature from measurements of the lime temperature over time. Second, we use BSI to reconstruct the initial condition of the lime from a measurement of its temperature later in time. We demonstrate the incorporation of prior information, visualize the posterior distributions of the parameter/initial condition, and show posterior samples of lime temperature trajectories from the model. Our Tutorial aims to reach a wide range of scientists and engineers.

    more » « less
  5. null (Ed.)
    Abstract Randomized methods can be competitive for the solution of problems with a large matrix of low rank. They also have been applied successfully to the solution of large-scale linear discrete ill-posed problems by Tikhonov regularization (Xiang and Zou in Inverse Probl 29:085008, 2013). This entails the computation of an approximation of a partial singular value decomposition of a large matrix A that is of numerical low rank. The present paper compares a randomized method to a Krylov subspace method based on Golub–Kahan bidiagonalization with respect to accuracy and computing time and discusses characteristics of linear discrete ill-posed problems that make them well suited for solution by a randomized method. 
    more » « less