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

Kirk M. Soodhalter

Kirk M. Soodhalter appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical AnalysisMathematical Software

Catalog footprint

What is connected

10works
3topics
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

10 published item(s)

preprint2022arXiv

A note on augmented unprojected Krylov subspace methods

Subspace recycling iterative methods and other subspace augmentation schemes are a successful extension to Krylov subspace methods in which a Krylov subspace is augmented with a fixed subspace spanned by vectors deemed to be helpful in accelerating convergence or conveying knowledge of the solution. Recently, a survey was published, in which a framework describing the vast majority of such methods was proposed [Soodhalter et al, GAMM-Mitt. 2020]. In many of these methods, the Krylov subspace is one generated by the system matrix composed with a projector that depends on the augmentation space. However, it is not a requirement that a projected Krylov subspace be used. There are augmentation methods built on using Krylov subspaces generated by the original system matrix, and these methods also fit into the general framework. In this note, we observe that one gains implementation benefits by considering such augmentation methods with unprojected Krylov subspaces in the general framework. We demonstrate this by applying the idea to the R$^3$GMRES method proposed in [Dong et al. ETNA 2014] to obtain a simplified implementation and to connect that algorithm to early augmentation schemes based on flexible preconditioning [Saad. SIMAX 1997].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Preconditioned infinite GMRES for parameterized linear systems

We are interested in obtaining approximate solutions to parameterized linear systems of the form $A(μ) x(μ) = b$ for many values of the parameter $μ$. Here $A(μ)$ is large, sparse, and nonsingular, with a nonlinear analytic dependence on $μ$. Our approach is based on a companion linearization for parameterized linear systems. The companion matrix is similar to the operator in the infinite Arnoldi method, and we use this to adapt the flexible GMRES setting. In this way, our method returns a function $\tilde{x}(μ)$ which is cheap to evaluate for different $μ$, and the preconditioner is applied only approximately. This novel approach leads to increased freedom to carry out the action of the operation inexactly, which provides performance improvement over the method infinite GMRES, without a loss of accuracy in general. We show that the error of our method is estimated based on the magnitude of the parameter $μ$, the inexactness of the preconditioning, and the spectrum of the linear companion matrix. Numerical examples from a finite element discretization of a Helmholtz equation with a parameterized material coefficient illustrate the competitiveness of our approach. The simulations are reproducible and publicly available online.

0 citations0 reviewsNo code linkedOpen access
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

Admissible and attainable convergence behavior of block Arnoldi and GMRES

It is well-established that any non-increasing convergence curve is possible for GMRES and a family of pairs $(A,b)$ can be constructed for which GMRES exhibits a given convergence curve with $A$ having arbitrary spectrum. No analog of this result has been established for block GMRES, wherein multiple right-hand sides are considered. By reframing the problem as a single linear system over a ring of square matrices, we develop convergence results for block Arnoldi and block GMRES. In particular, we show what convergence behavior is admissible for block GMRES and how the matrices and right-hand sides producing any admissible behavior can be constructed. Moreover, we show that the convergence of the block Arnoldi method for eigenvalue approximation can be almost fully independent of the convergence of block GMRES for the same coefficient matrix and the same starting vectors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A modified implementation of MINRES to monitor residual subvector norms for block systems

Saddle-point systems, i.e., structured linear systems with symmetric matrices are considered. A modified implementation of (preconditioned) MINRES is derived which allows to monitor the norms of the subvectors individually. Compared to the implementation from the textbook of [Elman, Sylvester and Wathen, Oxford University Press, 2014], our method requires one extra vector of storage and no additional applications of the preconditioner. Numerical experiments are included.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Stagnation of block GMRES and its relationship to block FOM

We analyze the the convergence behavior of block GMRES and characterize the phenomenon of stagnation which is then related to the behavior of the block FOM method. We generalize the block FOM method to generate well-defined approximations in the case that block FOM would normally break down, and these generalized solutions are used in our analysis. This behavior is also related to the principal angles between the column-space of the previous block GMRES residual and the current minimum residual constraint space. At iteration $j$, it is shown that the proper generalization of GMRES stagnation to the block setting relates to the columnspace of the $j$th block Arnoldi vector. Our analysis covers both the cases of normal iterations as well as block Arnoldi breakdown wherein dependent basis vectors are replaced with random ones. Numerical examples are given to illustrate what we have proven, including a small application problem to demonstrate the validity of the analysis in a less pathological case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Two recursive GMRES-type methods for shifted linear systems with general preconditioning

We present two minimum residual methods for solving sequences of shifted linear systems, the right-preconditioned shifted GMRES and shifted recycled GMRES algorithms which use a seed projection strategy often employed to solve multiple related problems. These methods are compatible with general preconditioning of all systems, and when restricted to right preconditioning, require no extra applications of the operator or preconditioner. These seed projection methods perform a minimum residual iteration for the base system while improving the approximations for the shifted systems at little additional cost. The iteration continues until the base system approximation is of satisfactory quality. The method is then recursively called for the remaining unconverged systems. We present both methods inside of a general framework which allows these techniques to be extended to the setting of flexible preconditioning and inexact Krylov methods. We present some analysis of such methods and numerical experiments demonstrating the effectiveness of the algorithms we have derived.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Block Krylov subspace recycling for shifted systems with unrelated right-hand sides

Many Krylov subspace methods for shifted linear systems take advantage of the invariance of the Krylov subspace under a shift of the matrix. However, exploiting this fact in the non-Hermitian case introduces restrictions; e.g., initial residuals must be collinear and this collinearity must be maintained at restart. Thus we cannot simultaneously solve shifted systems with unrelated right-hand sides using this strategy, and all shifted residuals cannot be simultaneously minimized over a Krylov subspace such that collinearity is maintained. It has been shown that this renders them generally incompatible with techniques of subspace recycling [Soodhalter et al. APNUM '14]. This problem, however, can be overcome. By interpreting a family of shifted systems as one Sylvester equation, we can take advantage of the known "shift invariance" of the Krylov subspace generated by the Sylvester operator. Thus we can simultaneously solve all systems over one block Krylov subspace using FOM or GMRES type methods, even when they have unrelated right-hand sides. Because residual collinearity is no longer a requirement at restart, these methods are fully compatible with subspace recycling techniques. Furthermore, we realize the benefits of block sparse matrix operations which arise in the context of high-performance computing applications. In this paper, we discuss exploiting this Sylvester equation point of view which has yielded methods for shifted systems which are compatible with unrelated right-hand sides. From this, we propose a recycled GMRES method for simultaneous solution of shifted systems.Numerical experiments demonstrate the effectiveness of the methods.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A block MINRES algorithm based on the banded Lanczos method

We develop a block minimum residual (MINRES) algorithm for symmetric indefinite matrices. This version is built upon the band Lanczos method that generates one basis vector of the block Krylov subspace per iteration rather than a whole block as in the block Lanczos process. However, we modify the method such that the most expensive operations are still performed in a block fashion. The benefit of using the band Lanczos method is that one can detect breakdowns from scalar values arising in the computation, allowing for a handling of breakdown which is straightforward to implement. We derive a progressive formulation of the MINRES method based on the band Lanczos process and give some implementation details. Specifically, a simple reordering of the steps allows us to perform many of the operations at the block level in order to take advantage of communication efficiencies offered by the block Lanczos process. This is an important concern in the context of next-generation super computing applications. We also present a technique allowing us to maintain the block size by replacing dependent Lanczos vectors with pregenerated random vectors whose orthogonality against all Lanczos vectors is maintained. Numerical results illustrate the performance on some sample problems. We present experiments that show how the relationship between right-hand sides can effect the performance of the method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Krylov Subspace Recycling for Sequences of Shifted Linear Systems

We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework. As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.

0 citations0 reviewsNo code linkedOpen access