ترغب بنشر مسار تعليمي؟ اضغط هنا

From low-rank approximation to an efficient rational Krylov subspace method for the Lyapunov equation

166   0   0.0 ( 0 )
 نشر من قبل Ivan Oseledets
 تاريخ النشر 2014
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We propose a new method for the approximate solution of the Lyapunov equation with rank-$1$ right-hand side, which is based on extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the connection between the Lyapunov equation, solution of systems of linear ODEs and alternating least squares method for low-rank approximation. The numerical experiments confirm the effectiveness of our approach.



قيم البحث

اقرأ أيضاً

New algorithms are proposed for the Tucker approximation of a 3-tensor, that access it using only the tensor-by-vector-by-vector multiplication subroutine. In the matrix case, Krylov methods are methods of choice to approximate the dominant column an d row subspaces of a sparse or structured matrix given through the matrix-by-vector multiplication subroutine. Using the Wedderburn rank reduction formula, we propose an algorithm of matrix approximation that computes Krylov subspaces and allows generalization to the tensor case. Several variants of proposed tensor algorithms differ by pivoting strategies, overall cost and quality of approximation. By convincing numerical experiments we show that the proposed methods are faster and more accurate than the minimal Krylov recursion, proposed recently by Elden and Savas.
This paper introduces new solvers for the computation of low-rank approximate solutions to large-scale linear problems, with a particular focus on the regularization of linear inverse problems. Although Krylov methods incorporating explicit projectio ns onto low-rank subspaces are already used for well-posed systems that arise from discretizing stochastic or time-dependent PDEs, we are mainly concerned with algorithms that solve the so-called nuclear norm regularized problem, where a suitable nuclear norm penalization on the solution is imposed alongside a fit-to-data term expressed in the 2-norm: this has the effect of implicitly enforcing low-rank solutions. By adopting an iteratively reweighted norm approach, the nuclear norm regularized problem is reformulated as a sequence of quadratic problems, which can then be efficiently solved using Krylov methods, giving rise to an inner-outer iteration scheme. Our approach differs from the other solvers available in the literature in that: (a) Kronecker product properties are exploited to define the reweighted 2-norm penalization terms; (b) efficient preconditioned Krylov methods replace gradient (projection) methods; (c) the regularization parameter can be efficiently and adaptively set along the iterations. Furthermore, we reformulate within the framework of flexible Krylov methods both the new inner-outer methods for nuclear norm regularization and some of the existing Krylov methods incorporating low-rank projections. This results in an even more computationally efficient (but heuristic) strategy, that does not rely on an inner-outer iteration scheme. Numerical experiments show that our new solvers are competitive with other state-of-the-art solvers for low-rank problems, and deliver reconstructions of increased quality with respect to other classical Krylov methods.
It has recently been demonstrated that dynamical low-rank algorithms can provide robust and efficient approximation to a range of kinetic equations. This is true especially if the solution is close to some asymptotic limit where it is known that the solution is low-rank. A particularly interesting case is the fluid dynamic limit that is commonly obtained in the limit of small Knudsen number. However, in this case the Maxwellian which describes the corresponding equilibrium distribution is not necessarily low-rank; because of this, the methods known in the literature are only applicable to the weakly compressible case. In this paper, we propose an efficient dynamical low-rank integrator that can capture the fluid limit -- the Navier-Stokes equations -- of the Boltzmann-BGK model even in the compressible regime. This is accomplished by writing the solution as $f=Mg$, where $M$ is the Maxwellian and the low-rank approximation is only applied to $g$. To efficiently implement this decomposition within a low-rank framework requires, in the isothermal case, that certain coefficients are evaluated using convolutions, for which fast algorithms are known. Using the proposed decomposition also has the advantage that the rank required to obtain accurate results is significantly reduced compared to the previous state of the art. We demonstrate this by performing a number of numerical experiments and also show that our method is able to capture sharp gradients/shock waves.
The paper is concerned with methods for computing the best low multilinear rank approximation of large and sparse tensors. Krylov-type methods have been used for this problem; here blo
We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework. As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا