Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights

The nonsymmetric Lanczos algorithm reduces a general matrix to tridiagonal by generating two sequences of vectors which satisfy a mutual bi-orthogonality property. The process can proceed as long as the two vectors generated at each stage are not mutually orthogonal, otherwise the process breaks down. In this paper, we propose a variant that does not break down by grouping the vectors into clusters and enforcing the bi-orthogonality property only between different clusters, but relaxing the property within clusters. We show how this variant of the matrix Lanczos algorithm applies directly to a problem of computing a set of orthogonal polynomials and associated indefinite weights with respect to an indefinite inner product, given the associated moments. We discuss the close relationship between the modified Lanczos algorithm and the modified Chebyshev algorithm. We further show the connection between this last problem and checksum-based error correction schemes for fault-tolerant computing.The research reported by this author was supported in part by NSF grant CCR-8813493.The research reported by this author was supported in part by ARO grant DAAL03-90-G-0105 and in part by NSF grant DCR-8412314.     

A rational Lanczos algorithm for model reduction

This paper presents a model reduction method for large-scale linear systems that is based on a Lanczos-type approach. A variant of the nonsymmetric Lanczos method, rational Lanczos, is shown to yield a rational interpolant (multi-point Padé approximant) for the large-scale system. An exact expression for the error in the interpolant is derived. Examples are utilized to demonstrate that the rational Lanczos method provides opportunities for significant improvements in the rate of convergence over single-point Lanczos approaches.     

A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment

We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn) ^2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion-planning problem, within the same running time. Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University.     

An implicit shift bidiagonalization algorithm for ill-posed systems

Iterative methods based on Lanczos bidiagonalization with full reorthogonalization (LBDR) are considered for solving large-scale discrete ill-posed linear least-squares problems of the form min _x Ax–b₂. Methods for regularization in the Krylov subspaces are discussed which use generalized cross validation (GCV) for determining the regularization parameter. These methods have the advantage that no a priori information about the noise level is required. To improve convergence of the Lanczos process we apply a variant of the implicitly restarted Lanczos algorithm by Sorensen using zero shifts. Although this restarted method simply corresponds to using LBDR with a starting vector (AA ^T) ^p b, it is shown that carrying out the process implicitly is essential for numerical stability. An LBDR algorithm is presented which incorporates implicit restarts to ensure that the global minimum of the CGV curve corresponds to a minimum on the curve for the truncated SVD solution. Numerical results are given comparing the performance of this algorithm with non-restarted LBDR.This work was partially supported by DARPA under grant 60NANB2D1272 and by the National Science Foundation under grant CCR-9209349.     

Almost tight upper bounds for the single cell and zone problems in three dimensions

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Israel Science Fund administered by the Israeli Academy of Sciences.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

求解病态线性方程组的收缩Lanczos方法

Lanczos方法是求解大型线性方程组的常用方法.遗憾的是,在Lanczos过程中通常会发生算法中断或数值不稳定的情况.将给出求解大型对称线性方程组的收缩Lanczos方法,即DLanczos方法.新算法将采用增广子空间技术,在Lanczos过程中向Krylov子空间加入少量绝对值较小的特征值所对应的特征向量进行收缩.数值实验表明,新算法比Lanczos方法收敛速度更快,并且适合求解病态对称线性方程组.     

An efficient method to set up a Lanczos based preconditioner for discrete ill-posed problems

Rezghi and Hosseini [M. Rezghi, S.M. Hosseini, Lanczos based preconditioner for discrete ill-posed problems, Computing 88 (2010) 79–96] presented a Lanczos based preconditioner for discrete ill-posed problems. Their preconditioner is constructed by using few steps (e.g., k) of the Lanczos bidiagonalization and corresponding computed singular values and right Lanczos vectors. In this article, we propose an efficient method to set up such preconditioner. Some numerical examples are given to show the effectiveness of the method.     

Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithm

In this text, we present a generalization of the idea of the Implicitly Restarted Arnoldi method to the unsymmetric Lanczos algorithm, using the two-sided Gram-Schmidt process or using a full Lanczos tridiagonalization. The resulting implicitly restarted Lanczos method is called Nested Lanczos. Nested Lanczos can be combined with an implicit filter. It can also be used in case of breakdown and offers an alternative for look-ahead. This revised version was published online in August 2006 with corrections to the Cover Date.     

隐式重启精化全局Lanczos方法

The numerical methods for solving large symmetric eigenvalue problems are considered in this paper.Based on the global Lanczos process,a global Lanczos method for solving large symmetric eigenvalue problems is presented.In order to accelerate the convergence of the F-Ritz vectors,the refined global Lanczos method is developed.Combining the implicitly restarted strategy with the deflation technique,an implicitly restarted and refined global Lanczos method for computing some eigenvalues of large symmetric matrices is proposed.Numerical results show that the proposed methods are efficient.     

计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法

The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.     

Area requirement and symmetry display of planar upward drawings

In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.Research supported in part by Cadre Technologies Inc., by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM), by the National Science Foundation under Grant CCR-9007851, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-83-K-0146 and ARPA order 6320, amendment 1, by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council, by the Texas Advanced Research Program under Grant No. 3972, and by the U.S. Army Research Office under Grant DAAL03-91-G-0035.     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

A matrix rational Lanczos method for model reduction in large‐scale first‐ and second‐order dynamical systems

In the present paper, we describe an adaptive modified rational global Lanczos algorithm for model‐order reduction problems using multipoint moment matching‐based methods. The major problem of these methods is the selection of some interpolation points. We first propose a modified rational global Lanczos process and then we derive Lanczos‐like equations for the global case. Next, we propose adaptive techniques for choosing the interpolation points. Second‐order dynamical systems are also considered in this paper, and the adaptive modified rational global Lanczos algorithm is applied to an equivalent state space model. Finally, some numerical examples will be given.     

Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

Euclid's algorithm and the Lanczos method over finite fields

This paper shows that there is a close relationship between the Euclidean algorithm for polynomials and the Lanczos method for solving sparse linear systems, especially when working over finite fields. It uses this relationship to account rigorously for the appearance of self-orthogonal vectors arising in the course of the Lanczos algorithm. It presents an improved Lanczos method which overcomes problems with self-orthogonality and compares this improved algorithm with the Euclidean algorithm.

     

求解陀螺系统特征值问题的收缩二阶Lanczos方法

本文研究陀螺系统特征值问题的数值解法,利用反对称矩阵Lanczos算法,提出了求解陀螺系统特征值问题的二阶Lanczos方法.基于提出的陀螺系统特征值问题的非等价低秩收缩技术,给出了计算陀螺系统极端特征值的收缩二阶Lanczos方法.数值结果说明了算法的有效性.     

Convergence estimates of nonrestarted and restarted block‐Lanczos methods

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.