A treatment of breakdowns and near breakdowns in a reduction of a matrix to upper J-Hessenberg form and related topics

摘要

The reduction of a matrix to an upper $J$-Hessenberg form is a crucial stepin the $SR$-algorithm (which is a $QR$-like algorithm), structure-preserving,for computing eigenvalues and vectors, for a class of structured matrices. This reduction may be handled via the algorithm JHESS or via the recentalgorithm JHMSH and its variants. The main drawback of JHESS (or JHMSH) is that it may suffer from a fatalbreakdown, causing a brutal stop of the computations and hence, the$SR$-algorithm does not run. JHESS may also encounter near-breakdowns, sourceof serious numerical instability. In this paper, we focus on these aspects. We first bring light on thenecessary and sufficient condition for the existence of the $SR$-decomposition,which is intimately linked to $J$-Hessenberg reduction. Then we will derive astrategy for curing fatal breakdowns and also for treating near breakdowns.Hence, the $J$-Hessenberg form may be obtained. Numerical experiments are given, demonstrating the efficiency of ourstrategies to cure and treat breakdowns or near breakdowns.