BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Eric de Sturler

Eric de Sturler appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical AnalysisComputational Engineering, Finance, and Sciencephysics.comp-phcond-mat.str-elmath.DSphysics.flu-dyn

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2020arXiv

A survey of subspace recycling iterative methods

This survey concerns subspace recycling methods, a popular class of iterative methods that enable effective reuse of subspace information in order to speed up convergence and find good initial guesses over a sequence of linear systems with slowly changing coefficient matrices, multiple right-hand sides, or both. The subspace information that is recycled is usually generated during the run of an iterative method (usually a Krylov subspace method) on one or more of the systems. Following introduction of definitions and notation, we examine the history of early augmentation schemes along with deflation preconditioning schemes and their influence on the development of recycling methods. We then discuss a general residual constraint framework through which many augmented Krylov and recycling methods can both be viewed. We review several augmented and recycling methods within this framework. We then discuss some known effective strategies for choosing subspaces to recycle before taking the reader through more recent developments that have generalized recycling for (sequences of) shifted linear systems, some of them with multiple right-hand sides in mind. We round out our survey with a brief review of application areas that have seen benefit from subspace recycling methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hybrid Projection Methods with Recycling for Inverse Problems

Iterative hybrid projection methods have proven to be very effective for solving large linear inverse problems due to their inherent regularizing properties as well as the added flexibility to select regularization parameters adaptively. In this work, we develop Golub-Kahan-based hybrid projection methods that can exploit compression and recycling techniques in order to solve a broad class of inverse problems where memory requirements or high computational cost may otherwise be prohibitive. For problems that have many unknown parameters and require many iterations, hybrid projection methods with recycling can be used to compress and recycle the solution basis vectors to reduce the number of solution basis vectors that must be stored, while obtaining a solution accuracy that is comparable to that of standard methods. If reorthogonalization is required, this may also reduce computational cost substantially. In other scenarios, such as streaming data problems or inverse problems with multiple datasets, hybrid projection methods with recycling can be used to efficiently integrate previously computed information for faster and better reconstruction. Additional benefits of the proposed methods are that various subspace selection and compression techniques can be incorporated, standard techniques for automatic regularization parameter selection can be used, and the methods can be applied multiple times in an iterative fashion. Theoretical results show that, under reasonable conditions, regularized solutions for our proposed recycling hybrid method remain close to regularized solutions for standard hybrid methods and reveal important connections among the resulting projection matrices. Numerical examples from image processing show the potential benefits of combining recycling with hybrid projection methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Randomization for the Efficient Computation of Parametric Reduced Order Models for Inversion

Nonlinear parametric inverse problems appear in many applications. Here, we focus on diffuse optical tomography (DOT) in medical imaging to recover unknown images of interest, such as cancerous tissue in a given medium, using a mathematical (forward) model. The forward model in DOT is a diffusion-absorption model for the photon flux. The main bottleneck in these problems is the repeated evaluation of the large-scale forward model. For DOT, this corresponds to solving large linear systems for each source and frequency at each optimization step. Moreover, Newton-type methods, often the method of choice, require additional linear solves with the adjoint to compute derivative information. Emerging technology allows for large numbers of sources and detectors, making these problems prohibitively expensive. Reduced order models (ROM) have been used to drastically reduce the system size in each optimization step, while solving the inverse problem accurately. However, for large numbers of sources and detectors, just the construction of the candidate basis for the ROM projection space incurs a substantial cost, as matching the full parameter gradient matrix in interpolatory model reduction requires large linear solves for all sources and frequencies and all detectors and frequencies for each parameter interpolation point. As this candidate basis numerically has low rank, this construction is followed by a rank-revealing factorization that typically reduces the number of vectors in the candidate basis substantially. We propose to use randomization to approximate this basis with a drastically reduced number of large linear solves. We also provide a detailed analysis for the low-rank structure of the candidate basis for our problem of interest. Even though we focus on the DOT problem, the ideas presented are relevant to many other large scale inverse problems and optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust Parameter Inversion using Adaptive Reduced Order Models

Nonlinear parametric inverse problems appear in many applications and are typically very expensive to solve, especially if they involve many measurements. These problems pose huge computational challenges as evaluating the objective function or misfit requires the solution of a large number of parameterized partial differential equations, typically one per source term. Newton-type algorithms, which may be required for fast convergence, typically require the additional solution of a large number of adjoint problems. The use of parametric model reduction may substantially alleviate this problem. In [de Sturler, E., Gugercin, S., Kilmer, M. E., Chaturantabut, S., Beattie, C., and O'Connell, M. (2015). Nonlinear Parametric Inversion Using Interpolatory Model Reduction. SIAM Journal on Scientific Computing, 37(3)], interpolatory model reduction was successfully used to drastically speed up inversion for Diffuse Optical Tomography (DOT). However, when using model reduction in high dimensional parameter spaces, obtaining error bounds in parameter space is typically intractable. In this paper, we propose to use stochastic estimates to remedy this problem. At the cost of one (randomized) full-scale linear solve per optimization step we obtain a robust algorithm. Moreover, since we can now update the model when needed, this robustness allows us to further reduce the order of the reduced order model and hence the cost of computing and using it, further decreasing the cost of inversion. We also propose a method to update the model reduction basis that reduces the number of large linear solves required by 46%-98% compared with the fixed reduced-order model. We demonstrate that this leads to a highly efficient and robust inversion method.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing Reduced Order Models via Inner-Outer Krylov Recycling in Diffuse Optical Tomography

In nonlinear imaging problems whose forward model is described by a partial differential equation (PDE), the main computational bottleneck in solving the inverse problem is the need to solve many large-scale discretized PDEs at each step of the optimization process. In the context of absorption imaging in diffuse optical tomography, one approach to addressing this bottleneck proposed recently (de Sturler, et al, 2015) reformulates the viewing of the forward problem as a differential algebraic system, and then employs model order reduction (MOR). However, the construction of the reduced model requires the solution of several full order problems (i.e. the full discretized PDE for multiple right-hand sides) to generate a candidate global basis. This step is then followed by a rank-revealing factorization of the matrix containing the candidate basis in order to compress the basis to a size suitable for constructing the reduced transfer function. The present paper addresses the costs associated with the global basis approximation in two ways. First, we use the structure of the matrix to rewrite the full order transfer function, and corresponding derivatives, such that the full order systems to be solved are symmetric (positive definite in the zero frequency case). Then we apply MOR to the new formulation of the problem. Second, we give an approach to computing the global basis approximation dynamically as the full order systems are solved. In this phase, only the incrementally new, relevant information is added to the existing global basis, and redundant information is not computed. This new approach is achieved by an inner-outer Krylov recycling approach which has potential use in other applications as well. We show the value of the new approach to approximate global basis computation on two DOT absorption image reconstruction problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Recycling BiCGSTAB with an Application to Parametric Model Order Reduction

Krylov subspace recycling is a process for accelerating the convergence of sequences of linear systems. Based on this technique, the recycling BiCG algorithm has been developed recently. Here, we now generalize and extend this recycling theory to BiCGSTAB. Recycling BiCG focuses on efficiently solving sequences of dual linear systems, while the focus here is on efficiently solving sequences of single linear systems (assuming non-symmetric matrices for both recycling BiCG and recycling BiCGSTAB). As compared with other methods for solving sequences of single linear systems with non-symmetric matrices (e.g., recycling variants of GMRES), BiCG based recycling algorithms, like recycling BiCGSTAB, have the advantage that they involve a short-term recurrence, and hence, do not suffer from storage issues and are also cheaper with respect to the orthogonalizations. We modify the BiCGSTAB algorithm to use a recycle space, which is built from left and right approximate invariant subspaces. Using our algorithm for a parametric model order reduction example gives good results. We show about 40% savings in the number of matrix-vector products and about 35% savings in runtime.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver

We focus on robust and efficient iterative solvers for the pressure Poisson equation in incompressible Navier-Stokes problems. Preconditioned Krylov subspace methods are popular for these problems, with BiCGStab and GMRES(m) most frequently used for nonsymmetric systems. BiCGStab is popular because it has cheap iterations, but it may fail for stiff problems, especially early on as the initial guess is far from the solution. Restarted GMRES is better, more robust, in this phase, but restarting may lead to very slow convergence. Therefore, we evaluate the rGCROT method for these systems. This method recycles a selected subspace of the search space (called recycle space) after a restart. This generally improves the convergence drastically compared with GMRES(m). Recycling subspaces is also advantageous for subsequent linear systems, if the matrix changes slowly or is constant. However, rGCROT iterations are still expensive in memory and computation time compared with those of BiCGStab. Hence, we propose a new, hybrid approach that combines the cheap iterations of BiCGStab with the robustness of rGCROT. For the first few time steps the algorithm uses rGCROT and builds an effective recycle space, and then it recycles that space in the rBiCGStab solver. We evaluate rGCROT on a turbulent channel flow problem, and we evaluate both rGCROT and the new, hybrid combination of rGCROT and rBiCGStab on a porous medium flow problem. We see substantial performance gains on both problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Efficient methods for computing observation impact in 4D-Var data assimilation

This paper presents a practical computational approach to quantify the effect of individual observations in estimating the state of a system. Such an analysis can be used for pruning redundant measurements, and for designing future sensor networks. The mathematical approach is based on computing the sensitivity of the reanalysis (unconstrained optimization solution) with respect to the data. The computational cost is dominated by the solution of a linear system, whose matrix is the Hessian of the cost function, and is only available in operator form. The right hand side is the gradient of a scalar cost function that quantifies the forecast error of the numerical model. The use of adjoint models to obtain the necessary first and second order derivatives is discussed. We study various strategies to accelerate the computation, including matrix-free iterative solvers, preconditioners, and an in-house multigrid solver. Experiments are conducted on both a small-size shallow-water equations model, and on a large-scale numerical weather prediction model, in order to illustrate the capabilities of the new methodology.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Nonlinear Parametric Inversion using Interpolatory Model Reduction

Nonlinear parametric inverse problems appear in several prominent applications; one such application is Diffuse Optical Tomography (DOT) in medical image reconstruction. Such inverse problems present huge computational challenges, mostly due to the need for solving a sequence of large-scale discretized, parametrized, partial differential equations (PDEs) in the forward model. In this paper, we show how interpolatory parametric model reduction can significantly reduce the cost of the inversion process in DOT by drastically reducing the computational cost of solving the forward problems. The key observation is that function evaluations for the underlying optimization problem may be viewed as transfer function evaluations along the imaginary axis; a similar observation holds for Jacobian evaluations as well. This motivates the use of system-theoretic model order reduction methods. We discuss the construction and use of interpolatory parametric reduced models as surrogates for the full forward model. Within the DOT setting, these surrogate models can approximate both the cost functional and the associated Jacobian with very little loss of accuracy while significantly reducing the cost of the overall inversion process. Four numerical examples illustrate the efficiency of the proposed approach. Although we focus on DOT in this paper, we believe that our approach is applicable much more generally.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Improved Scaling for Quantum Monte Carlo on Insulators

Quantum Monte Carlo (QMC) methods are often used to calculate properties of many body quantum systems. The main cost of many QMC methods, for example the variational Monte Carlo (VMC) method, is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators so that the cost of constructing Slater matrices in these systems is now linear in the number of particles, whereas computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing the determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution of this paper is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of ILUTP preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of QMC algorithms from O(n^3) per sweep to roughly O(n^2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. Our results show that preconditioned iterative solvers can dramatically reduce the cost of VMC for large(r) systems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Recycling BiCG with an Application to Model Reduction

Science and engineering problems frequently require solving a sequence of dual linear systems. Besides having to store only few Lanczos vectors, using the BiConjugate Gradient method (BiCG) to solve dual linear systems has advantages for specific applications. For example, using BiCG to solve the dual linear systems arising in interpolatory model reduction provides a backward error formulation in the model reduction framework. Using BiCG to evaluate bilinear forms -- for example, in quantum Monte Carlo (QMC) methods for electronic structure calculations -- leads to a quadratic error bound. Since our focus is on sequences of dual linear systems, we introduce recycling BiCG, a BiCG method that recycles two Krylov subspaces from one pair of dual linear systems to the next pair. The derivation of recycling BiCG also builds the foundation for developing recycling variants of other bi-Lanczos based methods, such as CGS, BiCGSTAB, QMR, and TFQMR. We develop an augmented bi-Lanczos algorithm and a modified two-term recurrence to include recycling in the iteration. The recycle spaces are approximate left and right invariant subspaces corresponding to the eigenvalues closest to the origin. These recycle spaces are found by solving a small generalized eigenvalue problem alongside the dual linear systems being solved in the sequence. We test our algorithm in two application areas. First, we solve a discretized partial differential equation (PDE) of convection-diffusion type. Such a problem provides well-known test cases that are easy to test and analyze further. Second, we use recycling BiCG in the Iterative Rational Krylov Algorithm (IRKA) for interpolatory model reduction. IRKA requires solving sequences of slowly changing dual linear systems. We show up to 70% savings in iterations, and also demonstrate that for a model reduction problem BiCG takes (about) 50% more time than recycling BiCG.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dynamic Adaptive Mesh Refinement for Topology Optimization

We present an improved method for topology optimization with both adaptive mesh refinement and derefinement. Since the total volume fraction in topology optimization is usually modest, after a few initial iterations the domain of computation is largely void. Hence, it is inefficient to have many small elements, in such regions, that contribute significantly to the overall computational cost but contribute little to the accuracy of computation and design. At the same time, we want high spatial resolution for accurate three-dimensional designs to avoid postprocessing or interpretation as much as possible. Dynamic adaptive mesh refinement (AMR) offers the possibility to balance these two requirements. We discuss requirements on AMR for topology optimization and the algorithmic features to implement them. The numerical design problems demonstrate (1) that our AMR strategy for topology optimization leads to designs that are equivalent to optimal designs on uniform meshes, (2) how AMR strategies that do not satisfy the postulated requirements may lead to suboptimal designs, and (3) that our AMR strategy significantly reduces the time to compute optimal designs.

0 citations0 reviewsNo code linkedOpen access