Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels
We present an efficient matrix-free point spread function (PSF) method for approximating operators that have locally supported non-negative integral kernels. The method computes impulse responses of the operator at scattered points, and interpolates these impulse responses to approximate integral ke...
Main Authors: | , , , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2023
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2307.03349 |
id |
ftarxivpreprints:oai:arXiv.org:2307.03349 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2307.03349 2023-09-05T13:20:19+02:00 Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels Alger, Nick Hartland, Tucker Petra, Noemi Ghattas, Omar 2023-07-06 http://arxiv.org/abs/2307.03349 unknown http://arxiv.org/abs/2307.03349 Mathematics - Numerical Analysis text 2023 ftarxivpreprints 2023-08-16T17:48:31Z We present an efficient matrix-free point spread function (PSF) method for approximating operators that have locally supported non-negative integral kernels. The method computes impulse responses of the operator at scattered points, and interpolates these impulse responses to approximate integral kernel entries. Impulse responses are computed by applying the operator to Dirac comb batches of point sources, which are chosen by solving an ellipsoid packing problem. Evaluation of kernel entries allows us to construct a hierarchical matrix (H-matrix) approximation of the operator. Further matrix computations are performed with H-matrix methods. We use the method to build preconditioners for the Hessian operator in two inverse problems governed by partial differential equations (PDEs): inversion for the basal friction coefficient in an ice sheet flow problem and for the initial condition in an advective-diffusive transport problem. While for many ill-posed inverse problems the Hessian of the data misfit term exhibits a low rank structure, and hence a low rank approximation is suitable, for many problems of practical interest the numerical rank of the Hessian is still large. But Hessian impulse responses typically become more local as the numerical rank increases, which benefits the PSF method. Numerical results reveal that the PSF preconditioner clusters the spectrum of the preconditioned Hessian near one, yielding roughly 5x-10x reductions in the required number of PDE solves, as compared to regularization preconditioning and no preconditioning. We also present a numerical study for the influence of various parameters (that control the shape of the impulse responses) on the effectiveness of the advection-diffusion Hessian approximation. The results show that the PSF-based preconditioners are able to form good approximations of high-rank Hessians using a small number of operator applications. Text Ice Sheet ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Mathematics - Numerical Analysis |
spellingShingle |
Mathematics - Numerical Analysis Alger, Nick Hartland, Tucker Petra, Noemi Ghattas, Omar Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
topic_facet |
Mathematics - Numerical Analysis |
description |
We present an efficient matrix-free point spread function (PSF) method for approximating operators that have locally supported non-negative integral kernels. The method computes impulse responses of the operator at scattered points, and interpolates these impulse responses to approximate integral kernel entries. Impulse responses are computed by applying the operator to Dirac comb batches of point sources, which are chosen by solving an ellipsoid packing problem. Evaluation of kernel entries allows us to construct a hierarchical matrix (H-matrix) approximation of the operator. Further matrix computations are performed with H-matrix methods. We use the method to build preconditioners for the Hessian operator in two inverse problems governed by partial differential equations (PDEs): inversion for the basal friction coefficient in an ice sheet flow problem and for the initial condition in an advective-diffusive transport problem. While for many ill-posed inverse problems the Hessian of the data misfit term exhibits a low rank structure, and hence a low rank approximation is suitable, for many problems of practical interest the numerical rank of the Hessian is still large. But Hessian impulse responses typically become more local as the numerical rank increases, which benefits the PSF method. Numerical results reveal that the PSF preconditioner clusters the spectrum of the preconditioned Hessian near one, yielding roughly 5x-10x reductions in the required number of PDE solves, as compared to regularization preconditioning and no preconditioning. We also present a numerical study for the influence of various parameters (that control the shape of the impulse responses) on the effectiveness of the advection-diffusion Hessian approximation. The results show that the PSF-based preconditioners are able to form good approximations of high-rank Hessians using a small number of operator applications. |
format |
Text |
author |
Alger, Nick Hartland, Tucker Petra, Noemi Ghattas, Omar |
author_facet |
Alger, Nick Hartland, Tucker Petra, Noemi Ghattas, Omar |
author_sort |
Alger, Nick |
title |
Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
title_short |
Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
title_full |
Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
title_fullStr |
Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
title_full_unstemmed |
Point spread function approximation of high rank Hessians with locally supported non-negative integral kernels |
title_sort |
point spread function approximation of high rank hessians with locally supported non-negative integral kernels |
publishDate |
2023 |
url |
http://arxiv.org/abs/2307.03349 |
genre |
Ice Sheet |
genre_facet |
Ice Sheet |
op_relation |
http://arxiv.org/abs/2307.03349 |
_version_ |
1776201008637018112 |