Wiley: Numerical Linear Algebra with Applications: Table of Contents
Table of Contents for Numerical Linear Algebra with Applications. List of articles from both the latest and EarlyView issues.
https://onlinelibrary.wiley.com/loi/10991506?af=R
Wiley: Numerical Linear Algebra with Applications: Table of Contents
Wiley
en-US
Numerical Linear Algebra with Applications
Numerical Linear Algebra with Applications
http://www.atypon.com/images/atypon_logo_small.gif
https://onlinelibrary.wiley.com/loi/10991506?af=R
Multigrid Methods 2017
Joel E.Dendy Jr.
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2164?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Multigrid Methods 2017
doi:10.1002/nla.2164
Numerical Linear Algebra with Applications
2018-02-14T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-14T08:00:00Z
2018-02-14T08:00:00Z
10.1002/nla.2164
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2164?af=R
Advances in implementation, theoretical motivation, and numerical results for the nested iteration with range decomposition algorithm
Summary
This paper studies a low‐communication algorithm for solving elliptic PDEs on high‐performance machines, the nested iteration with range decomposition (NIRD) algorithm. Previous work has shown that NIRD converges to a high level of accuracy within a small, fixed number of iterations (usually one or two) when applied to simple elliptic problems. This paper makes some improvements to the NIRD algorithm (including the addition of adaptivity during preprocessing, wider choice of partitioning functions, and modified error measurement) that enhance the method's accuracy and scalability, especially on more difficult problems. In addition, an updated convergence proof is presented based on heuristic assumptions that are supported by numerical evidence. Furthermore, a new performance model is developed that shows increased performance benefits for NIRD when problems are more expensive to solve using traditional methods. Finally, extensive testing on a variety of elliptic problems provides additional insight into the behavior of NIRD and additional evidence that NIRD achieves excellent convergence on a wide class of elliptic PDEs and, as such, should be a very competitive method for solving PDEs on large parallel computers.
WayneMitchell
,
TomManteuffel
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2149?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Advances in implementation, theoretical motivation, and numerical results for the nested iteration with range decomposition algorithm
doi:10.1002/nla.2149
Numerical Linear Algebra with Applications
2018-02-02T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-02T08:00:00Z
2018-02-02T08:00:00Z
10.1002/nla.2149
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2149?af=R
Comparison of algebraic multigrid methods for an adaptive space–time finite‐element discretization of the heat equation in 3D and 4D
Summary
The aim of this work is to compare algebraic multigrid (AMG) preconditioned GMRES methods for solving the nonsymmetric and positive definite linear systems of algebraic equations that arise from a space–time finite‐element discretization of the heat equation in 3D and 4D space–time domains. The finite‐element discretization is based on a Galerkin–Petrov variational formulation employing piecewise linear finite elements simultaneously in space and time. We focus on a performance comparison of conventional and modern AMG methods for such finite‐element equations, as well as robustness with respect to the mesh discretization and the heat capacity constant. We discuss different coarsening and interpolation strategies in the AMG methods for coarse‐grid selection and coarse‐grid matrix construction. Further, we compare AMG performance for the space–time finite‐element discretization on both uniform and adaptive meshes consisting of tetrahedra and pentachora in 3D and 4D, respectively. The mesh adaptivity occurring in space and time is guided by a residual‐based a posteriori error estimation.
OlafSteinbach
,
HuidongYang
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2143?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Comparison of algebraic multigrid methods for an adaptive space–time finite‐element discretization of the heat equation in 3D and 4D
doi:10.1002/nla.2143
Numerical Linear Algebra with Applications
2018-01-18T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-01-18T08:00:00Z
2018-01-18T08:00:00Z
10.1002/nla.2143
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2143?af=R
A geometric multigrid method for isogeometric compatible discretizations of the generalized Stokes and Oseen problems
Summary
In this paper, we present a geometric multigrid methodology for the solution of matrix systems associated with isogeometric compatible discretizations of the generalized Stokes and Oseen problems. The methodology provably yields a pointwise divergence‐free velocity field independent of the number of pre‐smoothing steps, postsmoothing steps, grid levels, or cycles in a V‐cycle implementation, provided that the initial velocity guess is also divergence free. The methodology relies upon Scwharz‐style smoothers in conjunction with specially defined overlapping subdomains that respect the underlying topological structure of the generalized Stokes and Oseen problems. Numerical results in both two‐ and three‐dimensions demonstrate the robustness of the methodology through the invariance of convergence rates with respect to grid resolution and flow parameters for the generalized Stokes problem and the generalized Oseen problem, provided that it is not advection dominated.
ChristopherColey
,
JosephBenzaken
,
John A.Evans
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2145?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
A geometric multigrid method for isogeometric compatible discretizations of the generalized Stokes and Oseen problems
doi:10.1002/nla.2145
Numerical Linear Algebra with Applications
2018-01-08T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-01-08T08:00:00Z
2018-01-08T08:00:00Z
10.1002/nla.2145
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2145?af=R
Scalable hierarchical PDE sampler for generating spatially correlated random fields using nonmatching meshes
Summary
This work describes a domain embedding technique between two nonmatching meshes used for generating realizations of spatially correlated random fields with applications to large‐scale sampling‐based uncertainty quantification. The goal is to apply the multilevel Monte Carlo (MLMC) method for the quantification of output uncertainties of PDEs with random input coefficients on general and unstructured computational domains. We propose a highly scalable, hierarchical sampling method to generate realizations of a Gaussian random field on a given unstructured mesh by solving a reaction–diffusion PDE with a stochastic right‐hand side. The stochastic PDE is discretized using the mixed finite element method on an embedded domain with a structured mesh, and then, the solution is projected onto the unstructured mesh. This work describes implementation details on how to efficiently transfer data from the structured and unstructured meshes at coarse levels, assuming that this can be done efficiently on the finest level. We investigate the efficiency and parallel scalability of the technique for the scalable generation of Gaussian random fields in three dimensions. An application of the MLMC method is presented for quantifying uncertainties of subsurface flow problems. We demonstrate the scalability of the sampling method with nonmatching mesh embedding, coupled with a parallel forward model problem solver, for large‐scale 3D MLMC simulations with up to 1.9·109 unknowns.
SarahOsborn
,
PatrickZulian
,
ThomasBenson
,
UmbertoVilla
,
RolfKrause
,
Panayot S.Vassilevski
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2146?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Scalable hierarchical PDE sampler for generating spatially correlated random fields using nonmatching meshes
doi:10.1002/nla.2146
Numerical Linear Algebra with Applications
2018-01-30T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-01-30T08:00:00Z
2018-01-30T08:00:00Z
10.1002/nla.2146
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2146?af=R
Local Fourier analysis of block‐structured multigrid relaxation schemes for the Stokes equations
Summary
Multigrid methods that use block‐structured relaxation schemes have been successfully applied to several saddle‐point problems, including those that arise from the discretization of the Stokes equations. In this paper, we present a local Fourier analysis of block‐structured relaxation schemes for the staggered finite‐difference discretization of the Stokes equations to analyze their convergence behavior. Three block‐structured relaxation schemes are considered: distributive relaxation, Braess–Sarazin relaxation, and Uzawa relaxation. In each case, we consider variants based on weighted‐Jacobi relaxation, as is most suitable for parallel implementation on modern architectures. From this analysis, optimal parameters are proposed, and we compare the efficiency of the presented algorithms with these parameters. Finally, some numerical experiments are presented to validate the two‐grid and multigrid convergence factors.
YunhuiHe
,
Scott P.MacLachlan
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2147?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Local Fourier analysis of block‐structured multigrid relaxation schemes for the Stokes equations
doi:10.1002/nla.2147
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/nla.2147
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2147?af=R
Exploring basal sliding with a fluidity‐based, ice‐sheet model using FOSLS
Summary
This paper develops two first‐order system—in this context, first‐order refers to the order of the PDE not to the model—least‐squares, fluidity‐based formulations of a nonlinear Stokes flow model for ice sheets that attempt to overcome the difficulties introduced by unbounded viscosity. One commonly used way to define viscosity, Glen's law, allows viscosity to become unbounded as the strain rates approach zero. Often, numerical approaches overcome these singularities by modifying viscosity to limit its maximum. The formulations in this paper, however, reframe the problem to avoid viscosity altogether by defining the system in terms of the inverse of viscosity, which is known as fluidity. This results in a quantity that approaches zero as viscosity approaches infinity. Additionally, a set of equations that represent the curl of the velocity gradient is added to help approximate the solution in a space closer to H1, which improves algebraic multigrid convergence. Previous research revealed that the first‐order system least‐squares formulation has difficulties in maintaining optimal discretization convergence on more complex domains. This paper discovers that this problem is linked to how the curl equations are scaled and that stronger scalings result in better solver performance but worse discretization convergence. Determining if there is an optimal scaling that balances performance and convergence is still an open question. Additionally, the fluidity‐based formulations are tested with three 2D benchmark problems. Two of these benchmark problems involve basal sliding and one involves a time‐dependent free surface. The fluidity‐based solutions are consistent with the standard Galerkin method using Taylor–hood elements while better resolving viscosity.
JefferyAllen
,
TomManteuffel
,
HariharRajaram
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2161?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Exploring basal sliding with a fluidity‐based, ice‐sheet model using FOSLS
doi:10.1002/nla.2161
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-03-14T07:00:00Z
2018-03-14T07:00:00Z
10.1002/nla.2161
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2161?af=R
A fully coupled two‐level Schwarz preconditioner based on smoothed aggregation for the transient multigroup neutron diffusion equations
Summary
The multigroup neutron diffusion equations (an approximation of the neutron transport equation) are widely used for studying the motion of neutrons and their interactions with stationary background materials. Solving the multigroup neutron diffusion equations is challenging because the unknowns are tightly coupled through scattering and fission events, and solutions with high spatial resolution of full reactor cores in multiphysics environments are frequently required. In this paper, we focus on the development of a scalable, parallel preconditioner for solving the system of equations arising from the finite‐element discretization of the multigroup neutron diffusion equations in space and an implicit finite‐difference scheme in time. The parallel preconditioner (here referred to as the “fully coupled Schwarz preconditioner”) is constructed by monolithically applying the overlapping domain decomposition method together with a smoothed aggregation‐based coarse space to the coupled system. Our approach is different from the traditional block Gauss–Seidel sweep method that applies the preconditioner from the fast group to the thermal group sequentially, and we demonstrate that it provides significant improvements in terms of both the number of iterations required and the total compute time for a system of equations with millions of unknowns on a large supercomputer.
FandeKong
,
YaqiWang
,
SebastianSchunert
,
John W.Peterson
,
Cody J.Permann
,
DavidAndrš
,
Richard C.Martineau
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2162?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
A fully coupled two‐level Schwarz preconditioner based on smoothed aggregation for the transient multigroup neutron diffusion equations
doi:10.1002/nla.2162
Numerical Linear Algebra with Applications
2018-02-14T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-14T08:00:00Z
2018-02-14T08:00:00Z
10.1002/nla.2162
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2162?af=R
Mixed
and
least‐squares finite element methods with application to linear hyperbolic problems
Summary
In this paper, a few dual least‐squares finite element methods and their application to scalar linear hyperbolic problems are studied. The purpose is to obtain L2‐norm approximations on finite element spaces of the exact solutions to hyperbolic partial differential equations of interest. This is approached by approximating the generally infeasible quadratic minimization that defines the L2‐orthogonal projection of the exact solution, by feasible least‐squares principles using the ideas of the original
method proposed in the context of elliptic equations. All methods in this paper are founded upon and extend the
approach that is rather general and applicable beyond the setting of elliptic problems. Error bounds are shown that point to the factors affecting the convergence and provide conditions that guarantee optimal rates. Furthermore, the preconditioning of the resulting linear systems is discussed. Numerical results are provided to illustrate the behavior of the methods on common finite element spaces.
Delyan Z.Kalchev
,
Thomas A.Manteuffel
,
SteffenMünzenmaier
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2150?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Mixed
and
least‐squares finite element methods with application to linear hyperbolic problems
doi:10.1002/nla.2150
Numerical Linear Algebra with Applications
2018-01-19T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-01-19T08:00:00Z
2018-01-19T08:00:00Z
10.1002/nla.2150
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2150?af=R
Algebraic multigrid for directed graph Laplacian linear systems (NS‐LAMG)
Summary
We propose nonsymmetric lean algebraic multigrid (NS‐LAMG), a new algebraic multigrid algorithm for directed graph Laplacian systems that combines ideas from undirected graph Laplacian multigrid solvers and multigrid algorithms for Markov chain stationary distribution systems. Low‐degree elimination, proposed in LAMG for undirected graphs, is generalized to directed graphs and is a key component of NS‐LAMG. In the setup phase, we propose a simple stationary‐aggregation multigrid algorithms for Markov chain stationary distribution systems solver enhanced by low‐degree elimination to find the right null‐space vector that is used for the intergrid transfer operators. Numerical results show that low‐degree elimination improves performance and that NS‐LAMG outperforms generalized minimal residual method with restart and stable bi‐conjugate gradient method for real‐world, directed graph Laplacian linear systems.
AlysonFox
,
ThomasManteuffel
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2152?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Algebraic multigrid for directed graph Laplacian linear systems (NS‐LAMG)
doi:10.1002/nla.2152
Numerical Linear Algebra with Applications
2018-01-31T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-01-31T08:00:00Z
2018-01-31T08:00:00Z
10.1002/nla.2152
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2152?af=R
Convergence of the multigrid reduction in time algorithm for the linear elasticity equations
Summary
This paper presents some recent advances for parallel‐in‐time methods applied to linear elasticity. With recent computer architecture changes leading to stagnant clock speeds, but ever increasing numbers of cores, future speedups will be available through increased concurrency. Thus, sequential algorithms, such as time stepping, will suffer a bottleneck. This paper explores multigrid reduction in time (MGRIT) for an important application area, linear elasticity. Previously, efforts at parallel‐in‐time for elasticity have experienced difficulties, for example, the beating phenomenon. As a result, practical parallel‐in‐time algorithms for this application area currently do not exist. This paper proposes some solutions made possible by MGRIT (e.g., slow temporal coarsening and FCF‐relaxation) and, more importantly, a different formulation of the problem that is more amenable to parallel‐in‐time methods. Using a recently developed convergence theory for MGRIT and Parareal, we show that the changed formulation of the problem avoids the instability issues and allows the reduction of the error using two temporal grids. We then extend our approach to the multilevel case, where we demonstrate how slow temporal coarsening improves convergence. The paper ends with supporting numerical results showing a practical algorithm enjoying speedup benefits over the sequential algorithm.
A.Hessenthaler
,
D.Nordsletten
,
O.Röhrle
,
J. B.Schroder
,
R. D.Falgout
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2155?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Convergence of the multigrid reduction in time algorithm for the linear elasticity equations
doi:10.1002/nla.2155
Numerical Linear Algebra with Applications
2018-02-14T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-14T08:00:00Z
2018-02-14T08:00:00Z
10.1002/nla.2155
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2155?af=R
Computing the diffusion state distance on graphs via algebraic multigrid and random projections
Summary
In this paper, we consider efficient and robust algorithms for computing the diffusion state distance (DSD) metric on graphs developed recently. In order to efficiently compute DSD, we reformulate the problem into graph Laplacians and use unsmoothed aggregation algebraic multigrid to solve the resulting linear system of equations. To further reduce the computational cost, we approximate DSD by using random projections based on the Johnson–Lindenstrauss lemma. Numerical results for real‐world protein–protein interaction networks are presented to demonstrate the efficiency and robustness of the proposed new approaches.
JunyuanLin
,
Lenore J.Cowen
,
BenjaminHescott
,
XiaozheHu
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2156?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Computing the diffusion state distance on graphs via algebraic multigrid and random projections
doi:10.1002/nla.2156
Numerical Linear Algebra with Applications
2018-02-07T08:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-02-07T08:00:00Z
2018-02-07T08:00:00Z
10.1002/nla.2156
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2156?af=R
Issue Information
No abstract is available for this article.
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2119?af=R
Numerical Linear Algebra with Applications, <a href="https://onlinelibrary.wiley.com/toc/10991506/25/3">Volume 25, Issue 3</a>, May 2018. <br/>
Numerical Linear Algebra with Applications, Volume 25, Issue 3, May 2018. <br/>
Issue Information
doi:10.1002/nla.2119
Numerical Linear Algebra with Applications
2018-04-06T07:00:00Z
Numerical Linear Algebra with Applications
25
3
2018-04-06T07:00:00Z
2018-04-06T07:00:00Z
10.1002/nla.2119
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2119?af=R
Bounds for the decay of the entries in inverses and Cauchy–Stieltjes functions of certain sparse, normal matrices
Summary
It is known that in many functions of banded and, more generally, sparse Hermitian positive definite matrices, the entries exhibit a rapid decay away from the sparsity pattern. This is particularly true for the inverse, and based on results for the inverse, bounds for Cauchy–Stieltjes functions of Hermitian positive definite matrices have recently been obtained. We add to the known results by considering certain types of normal matrices, for which fewer and typically less satisfactory results exist so far. Starting from a very general estimate based on approximation properties of Chebyshev polynomials on ellipses, we obtain as special cases insightful decay bounds for various classes of normal matrices, including (shifted) skew‐Hermitian and Hermitian indefinite matrices. In addition, some of our results improve over known bounds when applied to the Hermitian positive definite case.
AndreasFrommer
,
ClaudiaSchimmel
,
MarcelSchweitzer
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2131?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Bounds for the decay of the entries in inverses and Cauchy–Stieltjes functions of certain sparse, normal matrices
doi:10.1002/nla.2131
Numerical Linear Algebra with Applications
2017-11-24T08:00:00Z
Numerical Linear Algebra with Applications
2017-11-24T08:00:00Z
2017-11-24T08:00:00Z
10.1002/nla.2131
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2131?af=R
Numerical solution of Lyapunov equations related to Markov jump linear systems
Summary
We suggest and compare different methods for the numerical solution of Lyapunov‐like equations with application to control of Markovian jump linear systems. First, we consider fixed‐point iterations and associated Krylov subspace formulations. Second, we reformulate the equation as an optimization problem and consider steepest descent, conjugate gradient, and trust‐region methods. Numerical experiments illustrate that, for large‐scale problems, the trust‐region method is more efficient than a direct solution or a standard solver for linear matrix inequalities. The fixed‐point approach, however, is superior to the optimization methods. As an application, we consider a networked control system, where the Markov jumps are induced by the wireless communication protocol.
TobiasDamm
,
KazuhiroSato
,
AxelVierling
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2113?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical solution of Lyapunov equations related to Markov jump linear systems
doi:10.1002/nla.2113
Numerical Linear Algebra with Applications
2017-08-09T07:00:00Z
Numerical Linear Algebra with Applications
2017-08-09T07:00:00Z
2017-08-09T07:00:00Z
10.1002/nla.2113
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2113?af=R
On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes
Summary
Matrix equations of the kind A1X2+A0X+A−1=X, where both the matrix coefficients and the unknown are semi‐infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi‐Toeplitz matrices, are encountered in certain quasi‐birth–death processes as the tandem Jackson queue or in any other processes that can be modeled as a reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations that relies on semi‐infinite quasi‐Toeplitz matrix arithmetic. In particular, we show that the algorithm of cyclic reduction can be effectively applied and can approximate the infinite‐dimensional solutions with quadratic convergence at a cost that is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution and of the invariant probability measure of the associated quasi‐birth–death process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.
D. A.Bini
,
S.Massei
,
B.Meini
,
L.Robol
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2128?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes
doi:10.1002/nla.2128
Numerical Linear Algebra with Applications
2017-10-26T07:00:00Z
Numerical Linear Algebra with Applications
2017-10-26T07:00:00Z
2017-10-26T07:00:00Z
10.1002/nla.2128
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2128?af=R
Quasi‐HSS iteration methods for non‐Hermitian positive definite linear systems of strong skew‐Hermitian parts
Summary
For large sparse non‐Hermitian positive definite linear systems, we establish exact and inexact quasi‐HSS iteration methods and discuss their convergence properties. Numerical experiments show that both iteration methods are effective and robust when they are used either as linear solvers or as matrix splitting preconditioners for the Krylov subspace iteration methods. In addition, these two iteration methods are, respectively, much more powerful than the exact and inexact HSS iteration methods, especially when the linear systems have nearly singular Hermitian parts or strongly dominant skew‐Hermitian parts, and they can be employed to solve non‐Hermitian indefinite linear systems with only mild indefiniteness.
Zhong‐ZhiBai
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2116?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Quasi‐HSS iteration methods for non‐Hermitian positive definite linear systems of strong skew‐Hermitian parts
doi:10.1002/nla.2116
Numerical Linear Algebra with Applications
2017-09-27T07:00:00Z
Numerical Linear Algebra with Applications
2017-09-27T07:00:00Z
2017-09-27T07:00:00Z
10.1002/nla.2116
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2116?af=R
An alternating direction method of multipliers for the solution of matrix equations arising in inverse problems
Summary
In this paper, we consider an efficient approach to solve a linear ill‐posed inverse problem
with total variation regularization, where
has a Kronecker product structure,
. A numerical scheme is developed by using a variable splitting technique and directly exploiting the Kronecker structure of the problem. Experimental results on image restoration applications illustrate the effectiveness of our proposed method.
JianjunZhang
,
James G.Nagy
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2123?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
An alternating direction method of multipliers for the solution of matrix equations arising in inverse problems
doi:10.1002/nla.2123
Numerical Linear Algebra with Applications
2017-10-19T07:00:00Z
Numerical Linear Algebra with Applications
2017-10-19T07:00:00Z
2017-10-19T07:00:00Z
10.1002/nla.2123
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2123?af=R
A two‐phase strategy for control constrained elliptic optimal control problems
Summary
Elliptic optimal control problems with pointwise box constraints on the control are considered. To numerically solve elliptic optimal control problems with pointwise box constraints on the control, an inexact alternating direction method of multipliers (iADMM) is first proposed on the continuous level with the aim of solving discretized problems with moderate accuracy. Then, the standard piecewise linear finite element is employed to discretize the related subproblems appearing in each iteration of the iADMM algorithm. Such approach will give us the freedom to discretize two inner subproblems of the iADMM algorithm by different discretized scheme, respectively. More importantly, it should be emphasized that the discretized version of the iADMM algorithm can be regarded as a modification of the inexact semiproximal ADMM (isPADMM) algorithm. In order to obtain more accurate solution, the primal‐dual active set method is used as a postprocessor of the isPADMM. Numerical results not only show that the isPADMM and the two‐phase strategy are highly efficient but also show the mesh independence of the isPADMM.
Xiao‐LiangSong
,
BoYu
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2138?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
A two‐phase strategy for control constrained elliptic optimal control problems
doi:10.1002/nla.2138
Numerical Linear Algebra with Applications
2018-01-08T08:00:00Z
Numerical Linear Algebra with Applications
2018-01-08T08:00:00Z
2018-01-08T08:00:00Z
10.1002/nla.2138
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2138?af=R
Efficient solution of parameter‐dependent quasiseparable systems and computation of meromorphic matrix functions
Summary
In this paper, we focus on the solution of shifted quasiseparable systems and of more general parameter‐dependent matrix equations with quasiseparable representations. We propose an efficient algorithm exploiting the invariance of the quasiseparable structure under diagonal shifting and inversion. This algorithm is applied to compute various functions of matrices. Numerical experiments show that this approach is fast and numerically robust.
P.Boito
,
Y.Eidelman
,
L.Gemignani
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2141?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Efficient solution of parameter‐dependent quasiseparable systems and computation of meromorphic matrix functions
doi:10.1002/nla.2141
Numerical Linear Algebra with Applications
2018-01-18T08:00:00Z
Numerical Linear Algebra with Applications
2018-01-18T08:00:00Z
2018-01-18T08:00:00Z
10.1002/nla.2141
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2141?af=R
A block GMRES method with deflated restarting for solving linear systems with multiple shifts and multiple right‐hand sides
Summary
The restarted block generalized minimum residual method (BGMRES) with deflated restarting (BGMRES‐DR) was proposed by Morgan to dump the negative effect of small eigenvalues from the convergence of the BGMRES method. More recently, Wu et al. introduced the shifted BGMRES method (BGMRES‐Sh) for solving the sequence of linear systems with multiple shifts and multiple right‐hand sides. In this paper, a new shifted block Krylov subspace algorithm that combines the characteristics of both the BGMRES‐DR and the BGMRES‐Sh methods is proposed. Moreover, our method is enhanced with a seed selection strategy to handle the case of almost linear dependence of the right‐hand sides. Numerical experiments illustrate the potential of the proposed method to solve efficiently the sequence of linear systems with multiple shifts and multiple right‐hand sides, with and without preconditioner, also against other state‐of‐the‐art solvers.
Dong‐LinSun
,
Ting‐ZhuHuang
,
Yan‐FeiJing
,
BrunoCarpentieri
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2148?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
A block GMRES method with deflated restarting for solving linear systems with multiple shifts and multiple right‐hand sides
doi:10.1002/nla.2148
Numerical Linear Algebra with Applications
2018-01-18T08:00:00Z
Numerical Linear Algebra with Applications
2018-01-18T08:00:00Z
2018-01-18T08:00:00Z
10.1002/nla.2148
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2148?af=R
Computing the nearest stable matrix pairs
Summary
In this paper, we study the nearest stable matrix pair problem: given a square matrix pair (E,A), minimize the Frobenius norm of (ΔE,ΔA) such that (E+ΔE,A+ΔA) is a stable matrix pair. We propose a reformulation of the problem with a simpler feasible set by introducing dissipative Hamiltonian matrix pairs: A matrix pair (E,A) is dissipative Hamiltonian if A=(J−R)Q with skew‐symmetric J, positive semidefinite R, and an invertible Q such that QTE is positive semidefinite. This reformulation has a convex feasible domain onto which it is easy to project. This allows us to employ a fast gradient method to obtain a nearby stable approximation of a given matrix pair.
NicolasGillis
,
VolkerMehrmann
,
PunitSharma
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2153?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Computing the nearest stable matrix pairs
doi:10.1002/nla.2153
Numerical Linear Algebra with Applications
2018-02-01T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-01T08:00:00Z
2018-02-01T08:00:00Z
10.1002/nla.2153
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2153?af=R
BFGS‐like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming
Summary
We focus on efficient preconditioning techniques for sequences of Karush‐Kuhn‐Tucker (KKT) linear systems arising from the interior point (IP) solution of large convex quadratic programming problems. Constraint preconditioners (CPs), although very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the most time‐consuming task at each IP iteration. We overcome this problem by computing the CP from scratch only at selected IP iterations and by updating the last computed CP at the remaining iterations, via suitable low‐rank modifications based on a BFGS‐like formula. This work extends the limited‐memory preconditioners (LMPs) for symmetric positive definite matrices proposed by Gratton, Sartenaer and Tshimanga in 2011, by exploiting specific features of KKT systems and CPs. We prove that the updated preconditioners still belong to the class of exact CPs, thus allowing the use of the conjugate gradient method. Furthermore, they have the property of increasing the number of unit eigenvalues of the preconditioned matrix as compared with the generally used CPs. Numerical experiments are reported, which show the effectiveness of our updating technique when the cost for the factorization of the CP is high.
L.Bergamaschi
,
V.De Simone
,
D.diSerafino
,
A.Martínez
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2144?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
BFGS‐like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming
doi:10.1002/nla.2144
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/nla.2144
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2144?af=R
Staggered discontinuous Galerkin methods for the incompressible Navier–Stokes equations: Spectral analysis and computational results
Summary
The goal of this paper is to create a fruitful bridge between the numerical methods for approximating PDEs in fluid dynamics and the (iterative) numerical methods for dealing with the resulting large linear systems. Among the main objectives are the design of new, efficient iterative solvers and a rigorous analysis of their convergence speed. The link we have in mind is either the structure or the hidden structure that the involved coefficient matrices inherit, both from the continuous PDE and from the approximation scheme; in turn, the resulting structure is used for deducing spectral information, crucial for the conditioning and convergence analysis and for the design of more efficient solvers.
As a specific problem, we consider the incompressible Navier–Stokes equations; as a numerical technique, we consider a novel family of high‐order, accurate discontinuous Galerkin methods on staggered meshes, and as tools, we use the theory of Toeplitz matrices generated by a function (in the most general block, the multilevel form) and the more recent theory of generalized locally Toeplitz matrix sequences. We arrive at a somehow complete picture of the spectral features of the underlying matrices, and this information is employed for giving a forecast of the convergence history of the conjugate gradient method, together with a discussion on new and more advanced techniques (involving preconditioning, multigrid, multi‐iterative solvers). Several numerical tests are provided and critically illustrated in order to show the validity and the potential of our analysis.
M.Dumbser
,
F.Fambri
,
I.Furci
,
M.Mazza
,
S.Serra‐Capizzano
,
M.Tavelli
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2151?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Staggered discontinuous Galerkin methods for the incompressible Navier–Stokes equations: Spectral analysis and computational results
doi:10.1002/nla.2151
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/nla.2151
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2151?af=R
On structure preserving and circulant preconditioners for the space fractional coupled nonlinear Schrödinger equations
Summary
When the implicit, conservative difference scheme with the fractional centered difference formula is employed to discretize the space fractional coupled nonlinear Schrödinger equations, in each time step, we need to solve a complex symmetric linear system. The real part of the coefficient matrix is a symmetric Toeplitz‐plus‐diagonal matrix, whereas the imaginary part is the identity matrix. In this paper, a structure preserving preconditioner and a circulant preconditioner are proposed for such Toeplitz‐like matrix. Theoretically, tight bounds for eigenvalues of the preconditioned matrices are derived. Numerical implementations show that Krylov subspace iteration methods such as BiCGSTAB, when accelerated by the proposed preconditioners, are efficient solvers for solving the discretized linear system.
Jun‐GangWang
,
Yu‐HongRan
,
Dong‐LingWang
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2159?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
On structure preserving and circulant preconditioners for the space fractional coupled nonlinear Schrödinger equations
doi:10.1002/nla.2159
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/nla.2159
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2159?af=R
On compact vector formats in the solution of the chemical master equation with backward differentiation
Summary
A stochastic chemical system with multiple types of molecules interacting through reaction channels can be modeled as a continuous‐time Markov chain with a countably infinite multidimensional state space. Starting from an initial probability distribution, the time evolution of the probability distribution associated with this continuous‐time Markov chain is described by a system of ordinary differential equations, known as the chemical master equation (CME). This paper shows how one can solve the CME using backward differentiation. In doing this, a novel approach to truncate the state space at each time step using a prediction vector is proposed. The infinitesimal generator matrix associated with the truncated state space is represented compactly, and exactly, using a sum of Kronecker products of matrices associated with molecules. This exact representation is already compact and does not require a low‐rank approximation in the hierarchical Tucker decomposition (HTD) format. During transient analysis, compact solution vectors in HTD format are employed with the exact, compact, and truncated generated matrices in Kronecker form, and the linear systems are solved with the Jacobi method using fixed or adaptive rank control strategies on the compact vectors. Results of simulation on benchmark models are compared with those of the proposed solver and another version, which works with compact vectors and highly accurate low‐rank approximations of the truncated generator matrices in quantized tensor train format and solves the linear systems with the density matrix renormalization group method. Results indicate that there is a reason to solve the CME numerically, and adaptive rank control strategies on compact vectors in HTD format improve time and memory requirements significantly.
TuǧrulDayar
,
M. CanOrhan
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2158?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
On compact vector formats in the solution of the chemical master equation with backward differentiation
doi:10.1002/nla.2158
Numerical Linear Algebra with Applications
2018-02-08T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-08T08:00:00Z
2018-02-08T08:00:00Z
10.1002/nla.2158
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2158?af=R
Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols
Summary
It is known that for a tridiagonal Toeplitz matrix, having on the main diagonal the constant a0 and on the two first off‐diagonals the constants a1(lower) and a−1(upper), which are all complex values, there exist closed form formulas, giving the eigenvalues of the matrix and a set of associated eigenvectors. For example, for the 1D discrete Laplacian, this triple is (a0,a1,a−1)=(2,−1,−1). In the first part of this article, we consider a tridiagonal Toeplitz matrix of the same form (a0,aω,a−ω), but where the two off‐diagonals are positioned ω steps from the main diagonal instead of only one. We show that its eigenvalues and eigenvectors can also be identified in closed form and that interesting connections with the standard Toeplitz symbol are identified. Furthermore, as numerical evidences clearly suggest, it turns out that the eigenvalue behavior of a general banded symmetric Toeplitz matrix with real entries can be described qualitatively in terms of the symmetrically sparse tridiagonal case with real a0, aω=a−ω, ω=2,3,…, and also quantitatively in terms of those having monotone symbols. A discussion on the use of such results and on possible extensions complements the paper.
S.‐E.Ekström
,
S.Serra‐Capizzano
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2137?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols
doi:10.1002/nla.2137
Numerical Linear Algebra with Applications
2018-01-29T08:00:00Z
Numerical Linear Algebra with Applications
2018-01-29T08:00:00Z
2018-01-29T08:00:00Z
10.1002/nla.2137
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2137?af=R
Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations
Summary
For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.
Zhong‐ZhiBai
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2157?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations
doi:10.1002/nla.2157
Numerical Linear Algebra with Applications
2018-02-19T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-19T08:00:00Z
2018-02-19T08:00:00Z
10.1002/nla.2157
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2157?af=R
Domain decomposition approaches for accelerating contour integration eigenvalue solvers for symmetric eigenvalue problems
Summary
This paper discusses techniques for computing a few selected eigenvalue–eigenvector pairs of large and sparse symmetric matrices. A recently developed class of techniques to solve this type of problems is based on integrating the matrix resolvent operator along a complex contour that encloses the interval containing the eigenvalues of interest. This paper considers such contour integration techniques from a domain decomposition viewpoint and proposes two schemes. The first scheme can be seen as an extension of domain decomposition linear system solvers in the framework of contour integration methods for eigenvalue problems, such as FEAST. The second scheme focuses on integrating the resolvent operator primarily along the interface region defined by adjacent subdomains. A parallel implementation of the proposed schemes is described, and results on distributed computing environments are reported. These results show that domain decomposition approaches can lead to reduced run times and improved scalability.
VassilisKalantzis
,
JamesKestyn
,
EricPolizzi
,
YousefSaad
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2154?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Domain decomposition approaches for accelerating contour integration eigenvalue solvers for symmetric eigenvalue problems
doi:10.1002/nla.2154
Numerical Linear Algebra with Applications
2018-02-19T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-19T08:00:00Z
2018-02-19T08:00:00Z
10.1002/nla.2154
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2154?af=R
The conditioning of least‐squares problems in variational data assimilation
Summary
In variational data assimilation a least‐squares objective function is minimised to obtain the most likely state of a dynamical system. This objective function combines observation and prior (or background) data weighted by their respective error statistics. In numerical weather prediction, data assimilation is used to estimate the current atmospheric state, which then serves as an initial condition for a forecast. New developments in the treatment of observation uncertainties have recently been shown to cause convergence problems for this least‐squares minimisation. This is important for operational numerical weather prediction centres due to the time constraints of producing regular forecasts. The condition number of the Hessian of the objective function can be used as a proxy to investigate the speed of convergence of the least‐squares minimisation. In this paper we develop novel theoretical bounds on the condition number of the Hessian. These new bounds depend on the minimum eigenvalue of the observation error covariance matrix and the ratio of background error variance to observation error variance. Numerical tests in a linear setting show that the location of observation measurements has an important effect on the condition number of the Hessian. We identify that the conditioning of the problem is related to the complex interactions between observation error covariance and background error covariance matrices. Increased understanding of the role of each constituent matrix in the conditioning of the Hessian will prove useful for informing the choice of correlated observation error covariance matrix and observation location, particularly for practical applications.
Jemima M.Tabeart
,
Sarah L.Dance
,
Stephen A.Haben
,
Amos S.Lawless
,
Nancy K.Nichols
,
Joanne A.Waller
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2165?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
The conditioning of least‐squares problems in variational data assimilation
doi:10.1002/nla.2165
Numerical Linear Algebra with Applications
2018-02-23T08:00:00Z
Numerical Linear Algebra with Applications
2018-02-23T08:00:00Z
2018-02-23T08:00:00Z
10.1002/nla.2165
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2165?af=R
Convergence analysis of projected fixed‐point iteration on a low‐rank matrix manifold
Summary
In this paper, we analyze the convergence of a projected fixed‐point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method, we use the projector splitting scheme. We prove that the convergence rate of the projector splitting scheme is bounded by the convergence rate of standard fixed‐point iteration without rank constraints multiplied by the function of initial approximation. We also provide counterexample to the case when conditions of the theorem do not hold. Finally, we support our theoretical results with numerical experiments.
D. A.Kolesnikov
,
I. V.Oseledets
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2140?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Convergence analysis of projected fixed‐point iteration on a low‐rank matrix manifold
doi:10.1002/nla.2140
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
2018-03-14T07:00:00Z
10.1002/nla.2140
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2140?af=R
Scaled norm minimization method for computing the parameters of the HSS and the two‐parameter HSS preconditioners
Summary
The performance of the Hermitian and skew‐Hermitian splitting (HSS) preconditioner for the non‐Hermitian positive definite system of linear equations is largely dependent on the choice of its parameter value. In this work, an efficient scaled norm minimization (SNM) method is proposed to compute the parameter value of the HSS preconditioner. In addition, by choosing different parameters for the Hermitian and the skew‐Hermitian matrices in the HSS preconditioner, a two‐parameter HSS preconditioner is proposed. Moreover, an efficient and practical formula for computing the parameter values of this new preconditioner is also derived by using the SNM method. Numerical examples are illustrated to verify the performances of the HSS and the two‐parameter HSS preconditioners when their parameters are computed by the SNM method.
Ai‐LiYang
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2169?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Scaled norm minimization method for computing the parameters of the HSS and the two‐parameter HSS preconditioners
doi:10.1002/nla.2169
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
2018-03-14T07:00:00Z
10.1002/nla.2169
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2169?af=R
A posteriori error estimate for computing tr(f(A)) by using the Lanczos method
Summary
An outstanding problem when computing a function of a matrix, f(A), by using a Krylov method is to accurately estimate errors when convergence is slow. Apart from the case of the exponential function that has been extensively studied in the past, there are no well‐established solutions to the problem. Often, the quantity of interest in applications is not the matrix f(A) itself but rather the matrix–vector products or bilinear forms. When the computation related to f(A) is a building block of a larger problem (e.g., approximately computing its trace), a consequence of the lack of reliable error estimates is that the accuracy of the computed result is unknown. In this paper, we consider the problem of computing tr(f(A)) for a symmetric positive‐definite matrix A by using the Lanczos method and make two contributions: (a) an error estimate for the bilinear form associated with f(A) and (b) an error estimate for the trace of f(A). We demonstrate the practical usefulness of these estimates for large matrices and, in particular, show that the trace error estimate is indicative of the number of accurate digits. As an application, we compute the log determinant of a covariance matrix in Gaussian process analysis and underline the importance of error tolerance as a stopping criterion as a means of bounding the number of Lanczos steps to achieve a desired accuracy.
JieChen
,
YousefSaad
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2170?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
A posteriori error estimate for computing tr(f(A)) by using the Lanczos method
doi:10.1002/nla.2170
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
2018-03-14T07:00:00Z
10.1002/nla.2170
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2170?af=R
An efficient variant of HSS preconditioner for generalized saddle point problems
Summary
We present an efficient variant of the Hermitian and skew‐Hermitian splitting (HSS) preconditioner for generalized saddle point problems. By switching the positions of the two splitting matrices in the HSS preconditioner, together with some modifications combined with the relaxation preconditioning technique, we show that the new preconditioner is much closer to the coefficient matrix and easier to be implemented. Theoretical analyses show that the corresponding iteration method converges to the unique solution of the generalized saddle point problem under certain conditions. The spectral properties, including bounds on the eigenvalues and condition numbers of the eigenvectors, for the preconditioned matrix, are also discussed. Finally, numerical experiments are presented to illustrate the effectiveness of the new preconditioner.
Ju‐LiZhang
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2166?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
An efficient variant of HSS preconditioner for generalized saddle point problems
doi:10.1002/nla.2166
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
Numerical Linear Algebra with Applications
2018-03-14T07:00:00Z
2018-03-14T07:00:00Z
10.1002/nla.2166
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2166?af=R
Regularization matrices for discrete ill‐posed problems in several space dimensions
Summary
Many applications in science and engineering require the solution of large linear discrete ill‐posed problems that are obtained by the discretization of a Fredholm integral equation of the first kind in several space dimensions. The matrix that defines these problems is very ill conditioned and generally numerically singular, and the right‐hand side, which represents measured data, is typically contaminated by measurement error. Straightforward solution of these problems is generally not meaningful due to severe error propagation. Tikhonov regularization seeks to alleviate this difficulty by replacing the given linear discrete ill‐posed problem by a penalized least‐squares problem, whose solution is less sensitive to the error in the right‐hand side and to roundoff errors introduced during the computations. This paper discusses the construction of penalty terms that are determined by solving a matrix nearness problem. These penalty terms allow partial transformation to standard form of Tikhonov regularization problems that stem from the discretization of integral equations on a cube in several space dimensions.
LauraDykes
,
GuangxinHuang
,
SilviaNoschese
,
LotharReichel
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2163?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Regularization matrices for discrete ill‐posed problems in several space dimensions
doi:10.1002/nla.2163
Numerical Linear Algebra with Applications
2018-03-15T07:00:00Z
Numerical Linear Algebra with Applications
2018-03-15T07:00:00Z
2018-03-15T07:00:00Z
10.1002/nla.2163
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2163?af=R
Inverse generating function approach for the preconditioning of Toeplitz‐block systems
Summary
As proposed by R. H. Chan and M. K. Ng (1993), linear systems of the form T [ f ]x=b, where T [ f ] denotes the n×n Toeplitz matrix generated by the function f, can be solved using iterative solvers with
as a preconditioner. This article aims at generalizing this approach to the case of Toeplitz‐block matrices and matrix‐valued generating functions F. We prove that if F is Hermitian positive definite, most eigenvalues of the preconditioned matrix T [F−1]T[F] are clustered around one. Numerical experiments demonstrate the performance of this preconditioner.
F. S.Schneider
,
M.Pisarenco
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2168?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Inverse generating function approach for the preconditioning of Toeplitz‐block systems
doi:10.1002/nla.2168
Numerical Linear Algebra with Applications
2018-03-22T09:22:01Z
Numerical Linear Algebra with Applications
2018-03-22T09:22:01Z
2018-03-22T09:22:01Z
10.1002/nla.2168
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2168?af=R
Optimal solvers for linear systems with fractional powers of sparse SPD matrices
Summary
In this paper, we consider efficient algorithms for solving the algebraic equation
, 0<α<1, where
is a properly scaled symmetric and positive definite matrix obtained from finite difference or finite element approximations of second‐order elliptic problems in
, d=1,2,3. This solution is then written as
with
with β positive integer. The approximate solution method we propose and study is based on the best uniform rational approximation of the function tβ−α for 0<t≤1 and on the assumption that one has at hand an efficient method (e.g., multigrid, multilevel, or other fast algorithms) for solving equations such as
, c≥0. The provided numerical experiments confirm the efficiency of the proposed algorithms.
S.Harizanov
,
R.Lazarov
,
S.Margenov
,
P.Marinov
,
Y.Vutov
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2167?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Optimal solvers for linear systems with fractional powers of sparse SPD matrices
doi:10.1002/nla.2167
Numerical Linear Algebra with Applications
2018-03-22T09:22:48Z
Numerical Linear Algebra with Applications
2018-03-22T09:22:48Z
2018-03-22T09:22:48Z
10.1002/nla.2167
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2167?af=R
On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems
Summary
The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.
Zeng‐QiWang
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2172?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems
doi:10.1002/nla.2172
Numerical Linear Algebra with Applications
2018-03-26T03:10:46Z
Numerical Linear Algebra with Applications
2018-03-26T03:10:46Z
2018-03-26T03:10:46Z
10.1002/nla.2172
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2172?af=R
Distributed hierarchical SVD in the Hierarchical Tucker format
Summary
We consider tensors in the Hierarchical Tucker format and suppose the tensor data to be distributed among several compute nodes. We assume the compute nodes to be in a one‐to‐one correspondence with the nodes of the Hierarchical Tucker format such that connected nodes can communicate with each other. An appropriate tree structure in the Hierarchical Tucker format then allows for the parallelization of basic arithmetic operations between tensors with a parallel runtime that grows like
, where d is the tensor dimension. We introduce parallel algorithms for several tensor operations, some of which can be applied to solve linear equations
directly in the Hierarchical Tucker format using iterative methods such as conjugate gradients or multigrid. We present weak scaling studies, which provide evidence that the runtime of our algorithms indeed grows like
. Furthermore, we present numerical experiments in which we apply our algorithms to solve a parameter‐dependent diffusion equation in the Hierarchical Tucker format by means of a multigrid algorithm.
LarsGrasedyck
,
ChristianLöbbert
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2174?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Distributed hierarchical SVD in the Hierarchical Tucker format
doi:10.1002/nla.2174
Numerical Linear Algebra with Applications
2018-03-26T03:11:50Z
Numerical Linear Algebra with Applications
2018-03-26T03:11:50Z
2018-03-26T03:11:50Z
10.1002/nla.2174
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2174?af=R
Preordering saddle‐point systems for sparse LDLT factorization without pivoting
Summary
This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block LDLT factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.
SangyeLungten
,
Wil H.A.Schilders
,
Jennifer A.Scott
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2173?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Preordering saddle‐point systems for sparse LDLT factorization without pivoting
doi:10.1002/nla.2173
Numerical Linear Algebra with Applications
2018-03-26T03:11:26Z
Numerical Linear Algebra with Applications
2018-03-26T03:11:26Z
2018-03-26T03:11:26Z
10.1002/nla.2173
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2173?af=R
Perron‐based algorithms for the multilinear PageRank
Summary
We consider the multilinear PageRank problem, studied in a 2015 paper by Gleich, Lim and Yu, which is a system of quadratic equations with stochasticity and nonnegativity constraints. We use the theory of quadratic vector equations to prove several properties of its solutions and suggest new numerical algorithms. In particular, we prove the existence of a certain minimal solution, which does not always coincide with the stochastic one that is required by the problem. We use an interpretation of the solution as a Perron eigenvector to devise new fixed‐point algorithms for its computation and pair them with a continuation strategy based on a perturbative approach. The resulting numerical method is more reliable than the existing alternatives, being able to solve a larger number of problems.
BeatriceMeini
,
FedericoPoloni
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2177?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Perron‐based algorithms for the multilinear PageRank
doi:10.1002/nla.2177
Numerical Linear Algebra with Applications
2018-04-16T09:41:46Z
Numerical Linear Algebra with Applications
2018-04-16T09:41:46Z
2018-04-16T09:41:46Z
10.1002/nla.2177
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2177?af=R
Solving time‐periodic fractional diffusion equations via diagonalization technique and multigrid
Summary
This paper addresses numerical computation of time‐periodic diffusion equations with fractional Laplacian. Time‐periodic differential equations present fundamental challenges for numerical computation because we have to consider all the discrete solutions once in all instead of one by one. An idea based on the diagonalization technique is proposed, which yields a direct parallel‐in‐time computation for all the discrete solutions. The major computation cost is therefore reduced to solve a series of independent linear algebraic systems with complex coefficients, for which we apply a multigrid method using the damped Richardson iteration as the smoother. Such a linear solver possesses mesh‐independent convergence factor, and we make an optimization for the damping parameter to minimize such a constant convergence factor. Numerical results are provided to support our theoretical analysis.
Shu‐LinWu
,
HuiZhang
,
TaoZhou
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2178?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Solving time‐periodic fractional diffusion equations via diagonalization technique and multigrid
doi:10.1002/nla.2178
Numerical Linear Algebra with Applications
2018-04-16T11:16:34Z
Numerical Linear Algebra with Applications
2018-04-16T11:16:34Z
2018-04-16T11:16:34Z
10.1002/nla.2178
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2178?af=R
Domain decomposition preconditioners for multiscale problems in linear elasticity
Summary
We analyze two‐level overlapping Schwarz domain decomposition methods for vector‐valued piecewise linear finite element discretizations of the PDE system of linear elasticity. The focus of our study lies in the application to compressible, particle‐reinforced composites in 3D with large jumps in their material coefficients. We present coefficient‐explicit bounds for the condition number of the two‐level additive Schwarz preconditioned linear system. Thereby, we do not require that the coefficients are resolved by the coarse mesh. The bounds show a dependence of the condition number on the energy of the coarse basis functions, the coarse mesh, and the overlap parameters, as well as the coefficient variation. Similar estimates have been developed for scalar elliptic PDEs by Graham et al. The coarse spaces to which they apply here are assumed to contain the rigid body modes and can be considered as generalizations of the space of piecewise linear vector‐valued functions on a coarse triangulation. The developed estimates provide a concept for the construction of coarse spaces, which can lead to preconditioners that are robust with respect to high contrasts in Young's modulus and the Poisson ratio of the underlying composite. To confirm the sharpness of the theoretical findings, we present numerical results in 3D using vector‐valued linear, multiscale finite element and energy‐minimizing coarse spaces. The theory is not restricted to the isotropic (Lamé) case, extends to the full‐tensor case, and allows applications to multiphase materials with anisotropic constituents in two and three spatial dimensions. However, the bounds will depend on the ratio of largest to smallest eigenvalue of the elasticity tensor.
MarcoBuck
,
OlegIliev
,
HeikoAndrä
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2171?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Domain decomposition preconditioners for multiscale problems in linear elasticity
doi:10.1002/nla.2171
Numerical Linear Algebra with Applications
2018-04-20T10:37:10Z
Numerical Linear Algebra with Applications
2018-04-20T10:37:10Z
2018-04-20T10:37:10Z
10.1002/nla.2171
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2171?af=R
Accurate computations with collocation matrices of a general class of bases
Summary
In this paper, we provide algorithms for computing the bidiagonal decomposition of the collocation matrices of a very general class of bases of interest in computer‐aided geometric design and approximation theory. It is also shown that these algorithms can be used to perform accurately some algebraic computations with these matrices, such as the calculation of their inverses, their eigenvalues, or their singular values. Numerical experiments illustrate the results.
E.Mainar
,
J.M.Peña
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2184?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Accurate computations with collocation matrices of a general class of bases
doi:10.1002/nla.2184
Numerical Linear Algebra with Applications
2018-04-23T02:06:55Z
Numerical Linear Algebra with Applications
2018-04-23T02:06:55Z
2018-04-23T02:06:55Z
10.1002/nla.2184
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2184?af=R
Computational Krylov‐based methods for large‐scale differential Sylvester matrix problems
Summary
In the present paper, we propose Krylov‐based methods for solving large‐scale differential Sylvester matrix equations having a low‐rank constant term. We present two new approaches for solving such differential matrix equations. The first approach is based on the integral expression of the exact solution and a Krylov method for the computation of the exponential of a matrix times a block of vectors. In the second approach, we first project the initial problem onto a block (or extended block) Krylov subspace and get a low‐dimensional differential Sylvester matrix equation. The latter problem is then solved by some integration numerical methods such as the backward differentiation formula or Rosenbrock method, and the obtained solution is used to build the low‐rank approximate solution of the original problem. We give some new theoretical results such as a simple expression of the residual norm and upper bounds for the norm of the error. Some numerical experiments are given in order to compare the two approaches.
M.Hached
,
K.Jbilou
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2187?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Computational Krylov‐based methods for large‐scale differential Sylvester matrix problems
doi:10.1002/nla.2187
Numerical Linear Algebra with Applications
2018-04-23T02:13:14Z
Numerical Linear Algebra with Applications
2018-04-23T02:13:14Z
2018-04-23T02:13:14Z
10.1002/nla.2187
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2187?af=R
Multilevel approaches for FSAI preconditioning
Summary
Factorized sparse approximate inverse (FSAI) preconditioners are robust algorithms for symmetric positive matrices, which are particularly attractive in a parallel computational environment because of their inherent and almost perfect scalability. Their parallel degree is even redundant with respect to the actual capabilities of the current computational architectures. In this work, we present two new approaches for FSAI preconditioners with the aim of improving the algorithm effectiveness by adding some sequentiality to the native formulation. The first one, denoted as block tridiagonal FSAI, is based on a block tridiagonal factorization strategy, whereas the second one, domain decomposition FSAI, is built by reordering the matrix graph according to a multilevel k‐way partitioning method followed by a bandwidth minimization algorithm. We test these preconditioners by solving a set of symmetric positive definite problems arising from different engineering applications. The results are evaluated in terms of performance, scalability, and robustness, showing that both strategies lead to faster convergent schemes regarding the number of iterations and total computational time in comparison with the native FSAI with no significant loss in the algorithmic parallel degree.
Victor A. P.Magri
,
AndreaFranceschini
,
MassimilianoFerronato
,
CarloJanna
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2183?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Multilevel approaches for FSAI preconditioning
doi:10.1002/nla.2183
Numerical Linear Algebra with Applications
2018-04-25T07:21:00Z
Numerical Linear Algebra with Applications
2018-04-25T07:21:00Z
2018-04-25T07:21:00Z
10.1002/nla.2183
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2183?af=R
Convergence estimates of nonrestarted and restarted block‐Lanczos methods
Summary
The block‐Lanczos method serves to compute a moderate number of eigenvalues and the corresponding invariant subspace of a symmetric matrix. In this paper, the convergence behavior of nonrestarted and restarted versions of the block‐Lanczos method is analyzed. For the nonrestarted version, we improve an estimate by Saad by means of a change of the auxiliary vector so that the new estimate is much more accurate in the case of clustered or multiple eigenvalues. For the restarted version, an estimate by Knyazev is generalized by extending our previous results on block steepest descent iterations and single‐vector restarted Krylov subspace iterations. The new estimates can also be reformulated and applied to invert‐block‐Lanczos methods for solving generalized matrix eigenvalue problems.
MingZhou
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2182?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Convergence estimates of nonrestarted and restarted block‐Lanczos methods
doi:10.1002/nla.2182
Numerical Linear Algebra with Applications
2018-04-26T10:11:52Z
Numerical Linear Algebra with Applications
2018-04-26T10:11:52Z
2018-04-26T10:11:52Z
10.1002/nla.2182
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2182?af=R
Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves
Summary
The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.
BrendanGavin
,
EricPolizzi
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2188?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves
doi:10.1002/nla.2188
Numerical Linear Algebra with Applications
2018-04-26T07:00:00Z
Numerical Linear Algebra with Applications
2018-04-26T07:00:00Z
2018-04-26T07:00:00Z
10.1002/nla.2188
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2188?af=R
Krylov methods for low‐rank commuting generalized Sylvester equations
Summary
We consider generalizations of the Sylvester matrix equation, consisting of the sum of a Sylvester operator and a linear operator Π with a particular structure. More precisely, the commutators of the matrix coefficients of the operator Π and the Sylvester operator coefficients are assumed to be matrices with low rank. We show (under certain additional conditions) low‐rank approximability of this problem, that is, the solution to this matrix equation can be approximated with a low‐rank matrix. Projection methods have successfully been used to solve other matrix equations with low‐rank approximability. We propose a new projection method for this class of matrix equations. The choice of the subspace is a crucial ingredient for any projection method for matrix equations. Our method is based on an adaption and extension of the extended Krylov subspace method for Sylvester equations. A constructive choice of the starting vector/block is derived from the low‐rank commutators. We illustrate the effectiveness of our method by solving large‐scale matrix equations arising from applications in control theory and the discretization of PDEs. The advantages of our approach in comparison to other methods are also illustrated.
EliasJarlebring
,
GiampaoloMele
,
DavidePalitta
,
EmilRingh
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2176?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Krylov methods for low‐rank commuting generalized Sylvester equations
doi:10.1002/nla.2176
Numerical Linear Algebra with Applications
2018-04-27T01:07:37Z
Numerical Linear Algebra with Applications
2018-04-27T01:07:37Z
2018-04-27T01:07:37Z
10.1002/nla.2176
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2176?af=R
Symmetric orthogonal approximation to symmetric tensors with applications to image reconstruction
Summary
The main objective of this paper is to study an approximation of symmetric tensors by symmetric orthogonal decomposition. We propose and study an iterative algorithm to determine a symmetric orthogonal approximation and analyze the convergence of the proposed algorithm. Numerical examples are reported to demonstrate the effectiveness of the proposed algorithm. We also apply the proposed algorithm to represent correlated face images. We demonstrate better face image reconstruction results by combining principal components and symmetric orthogonal approximation instead of combining principal components and higher‐order SVD results.
JunjunPan
,
Michael K.Ng
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2180?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Symmetric orthogonal approximation to symmetric tensors with applications to image reconstruction
doi:10.1002/nla.2180
Numerical Linear Algebra with Applications
2018-04-30T01:56:11Z
Numerical Linear Algebra with Applications
2018-04-30T01:56:11Z
2018-04-30T01:56:11Z
10.1002/nla.2180
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2180?af=R
Two‐step Newton‐type methods for solving inverse eigenvalue problems
Summary
In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.
Xiao ShanChen
,
Chao TaoWen
,
Hai‐weiSun
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2185?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Two‐step Newton‐type methods for solving inverse eigenvalue problems
doi:10.1002/nla.2185
Numerical Linear Algebra with Applications
2018-05-04T08:10:10Z
Numerical Linear Algebra with Applications
2018-05-04T08:10:10Z
2018-05-04T08:10:10Z
10.1002/nla.2185
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2185?af=R
Compact representation of the full Broyden class of quasi‐Newton updates
Summary
In this paper, we present the compact representation for matrices belonging to the Broyden class of quasi‐Newton updates, where each update may be either rank one or rank two. This work extends previous results solely for the restricted Broyden class of rank‐two updates. In this article, it is not assumed that the same Broyden update is used in each iteration; rather, different members of the Broyden class may be used in each iteration. Numerical experiments suggest that a practical implementation of the compact representation is able to accurately represent matrices belonging to the Broyden class of updates. Furthermore, we demonstrate how to compute the compact representation for the inverse of these matrices and a practical algorithm for solving linear systems with members of the Broyden class of updates. We demonstrate through numerical experiments that the proposed linear solver is able to efficiently solve linear systems with members of the Broyden class of matrices with high accuracy. As an immediate consequence of this work, it is now possible to efficiently compute the eigenvalues of any limited‐memory member of the Broyden class of matrices, allowing for the computation of condition numbers and the ability to perform sensitivity analysis.
OmarDeGuchy
,
Jennifer B.Erway
,
Roummel F.Marcia
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2186?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Compact representation of the full Broyden class of quasi‐Newton updates
doi:10.1002/nla.2186
Numerical Linear Algebra with Applications
2018-05-07T07:00:00Z
Numerical Linear Algebra with Applications
2018-05-07T07:00:00Z
2018-05-07T07:00:00Z
10.1002/nla.2186
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2186?af=R
A randomized tensor singular value decomposition based on the t‐product
Summary
The tensor SVD (t‐SVD) for third‐order tensors, previously proposed in the literature, has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well‐known randomized matrix method to the t‐SVD. This method can produce a factorization with similar properties to the t‐SVD, but it is more computationally efficient on very large data sets. We present details of the algorithms and theoretical results and provide numerical results that show the promise of our approach for compressing and analyzing image‐based data sets. We also present an improved analysis of the randomized and simultaneous iteration for matrices, which may be of independent interest to the scientific community. We also use these new results to address the convergence properties of the new and randomized tensor method as well.
JianiZhang
,
Arvind K.Saibaba
,
Misha E.Kilmer
,
ShuchinAeron
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2179?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
A randomized tensor singular value decomposition based on the t‐product
doi:10.1002/nla.2179
Numerical Linear Algebra with Applications
2018-05-09T07:00:00Z
Numerical Linear Algebra with Applications
2018-05-09T07:00:00Z
2018-05-09T07:00:00Z
10.1002/nla.2179
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2179?af=R
A Riemannian trust‐region method for low‐rank tensor completion
Summary
The goal of tensor completion is to fill in missing entries of a partially known tensor (possibly including some noise) under a low‐rank constraint. This may be formulated as a least‐squares problem. The set of tensors of a given multilinear rank is known to admit a Riemannian manifold structure; thus, methods of Riemannian optimization are applicable. In our work, we derive the Riemannian Hessian of an objective function on the low‐rank tensor manifolds using the Weingarten map, a concept from differential geometry. We discuss the convergence properties of Riemannian trust‐region methods based on the exact Hessian and standard approximations, both theoretically and numerically. We compare our approach with Riemannian tensor completion methods from recent literature, both in terms of convergence behavior and computational complexity. Our examples include the completion of randomly generated data with and without noise and the recovery of multilinear data from survey statistics.
GennadijHeidel
,
VolkerSchulz
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2175?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
A Riemannian trust‐region method for low‐rank tensor completion
doi:10.1002/nla.2175
Numerical Linear Algebra with Applications
2018-05-17T01:10:52Z
Numerical Linear Algebra with Applications
2018-05-17T01:10:52Z
2018-05-17T01:10:52Z
10.1002/nla.2175
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2175?af=R
Perturbation analysis in finite LD‐QBD processes and applications to epidemic models
Summary
In this paper, our interest is in the perturbation analysis of level‐dependent quasi‐birth‐and‐death (LD‐QBD) processes, which constitute a wide class of structured Markov chains. An LD‐QBD process has the special feature that its space of states can be structured by levels (groups of states), so that a tridiagonal‐by‐blocks structure is obtained for its infinitesimal generator. For these processes, a number of algorithmic procedures exist in the literature in order to compute several performance measures while exploiting the underlying matrix structure; among others, these measures are related to first‐passage times to a certain level L(0) and hitting probabilities at this level, the maximum level visited by the process before reaching states of level L(0), and the stationary distribution. For the case of a finite number of states, our aim here is to develop analogous algorithms to the ones analyzing these measures, for their perturbation analysis. This approach uses matrix calculus and exploits the specific structure of the infinitesimal generator, which allows us to obtain additional information during the perturbation analysis of the LD‐QBD process by dealing with specific matrices carrying probabilistic insights of the dynamics of the process. We illustrate the approach by means of applying multitype versions of the susceptible‐infective (SI) and susceptible‐infective‐susceptible (SIS) epidemic models to the spread of antibiotic‐sensitive and antibiotic‐resistant bacterial strains in a hospital ward.
A.Gómez‐Corral
,
M.López‐García
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2160?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Perturbation analysis in finite LD‐QBD processes and applications to epidemic models
doi:10.1002/nla.2160
Numerical Linear Algebra with Applications
2018-03-05T08:00:00Z
Numerical Linear Algebra with Applications
2018-03-05T08:00:00Z
2018-03-05T08:00:00Z
10.1002/nla.2160
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2160?af=R
Editorial: Novel methods and theories in numerical algebra with interdisciplinary applications
Zhong‐ZhiBai
,
Maya G.Neytcheva
,
LotharReichel
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2181?af=R
Numerical Linear Algebra with Applications, EarlyView. <br/>
Numerical Linear Algebra with Applications, EarlyView. <br/>
Editorial: Novel methods and theories in numerical algebra with interdisciplinary applications
doi:10.1002/nla.2181
Numerical Linear Algebra with Applications
2018-04-16T03:53:55Z
Numerical Linear Algebra with Applications
2018-04-16T03:53:55Z
2018-04-16T03:53:55Z
10.1002/nla.2181
https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2181?af=R