Bisection acceleration for the symmetric tridiagonal eigenvalue problem

We present new algorithms that accelerate the bisection method for the symmetric tridiagonal eigenvalue problem. The algorithms rely on some new techniques, including a new variant of Newton's iteration that reaches cubic convergence (right from the start) to the well separated eigenvalues and can be further applied to acceleration of some other iterative processes, in particular, of the divide-and-conquer methods for the symmetric tridiagonal eigenvalue problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Enhanced algebraic substructuring for symmetric generalized eigenvalue problems

This article proposes a new substructuring algorithm to approximate the algebraically smallest eigenvalues and corresponding eigenvectors of a symmetric positive-definite matrix pencil $(A,M)$. The proposed approach partitions the graph associated with $(A,M)$ into a number of algebraic substructures and builds a Rayleigh–Ritz projection subspace by combining spectral information associated with the interior and interface variables of the algebraic domain. The subspace associated with interior variables is built by computing substructural eigenvectors and truncated Neumann series expansions of resolvent matrices. The subspace associated with interface variables is built by computing eigenvectors and associated leading derivatives of linearized spectral Schur complements. The proposed algorithm can take advantage of multilevel partitionings when the size of the pencil. Experiments performed on problems stemming from discretizations of model problems showcase the efficiency of the proposed algorithm and verify that adding eigenvector derivatives can enhance the overall accuracy of the approximate eigenpairs, especially those associated with eigenvalues located near the origin.     

A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

Algebraic formulations for the solution of the nullspace‐free eigenvalue problem using the inexact Shift‐and‐Invert Lanczos method

Given the generalized symmetric eigenvalue problem Ax=λMx, with A semidefinite and M definite, we analyse some algebraic formulations for the approximation of the smallest non‐zero eigenpairs, assuming that a sparse basis for the null space is available. In particular, we consider the inexact version of the Shift‐and‐Invert Lanczos method, and we show that apparently different algebraic formulations provide the same approximation iterates, under some natural hypotheses. Our results suggest that alternative strategies need to be explored to really take advantage of the special problem setting, other than reformulating the algebraic problem. Experiments on a real application problem corroborate our theoretical findings. Copyright © 2002 John Wiley & Sons, Ltd.     

Mass‐lumping or not mass‐lumping for eigenvalue problems

In this article we analyze the effect of mass‐lumping in the linear triangular finite element approximation of second‐order elliptic eigenvalue problems. We prove that the eigenvalue obtained by using mass‐lumping is always below the one obtained with exact integration. For singular eigenfunctions, as those arising in non convex polygons, we prove that the eigenvalue obtained with mass‐lumping is above the exact eigenvalue when the mesh size is small enough. So, we conclude that the use of mass‐lumping is convenient in the singular case. When the eigenfunction is smooth several numerical experiments suggest that the eigenvalue computed with mass‐lumping is below the exact one if the mesh is not too coarse. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 653–664, 2003     

Numerical methods for palindromic eigenvalue problems: Computing the anti‐triangular Schur form

We present structure‐preserving numerical methods for the eigenvalue problem of complex palindromic pencils. Such problems arise in control theory, as well as from palindromic linearizations of higher degree palindromic matrix polynomials. A key ingredient of these methods is the development of an appropriate condensed form—the anti‐triangular Schur form. Ill‐conditioned problems with eigenvalues near the unit circle, in particular near ±1, are discussed. We show how a combination of unstructured methods followed by a structured refinement can be used to solve such problems accurately. Copyright © 2008 John Wiley & Sons, Ltd.     

Inertia‐based spectrum slicing for symmetric quadratic eigenvalue problems

In the quadratic eigenvalue problem (QEP) with all coefficient matrices symmetric, there can be complex eigenvalues. However, some applications need to compute real eigenvalues only. We propose a Lanczos‐based method for computing all real eigenvalues contained in a given interval of large‐scale symmetric QEPs. The method uses matrix inertias of the quadratic polynomial evaluated at different shift values. In this way, for hyperbolic problems, it is possible to make sure that all eigenvalues in the interval have been computed. We also discuss the general nonhyperbolic case. Our implementation is memory‐efficient by representing the computed pseudo‐Lanczos basis in a compact tensor product representation. We show results of computational experiments with a parallel implementation in the SLEPc library.     

A practical method for computing the largest M‐eigenvalue of a fourth‐order partially symmetric tensor

In this paper, we consider a bi‐quadratic homogeneous polynomial optimization problem over two unit spheres arising in nonlinear elastic material analysis and in entanglement studies in quantum physics. The problem is equivalent to computing the largest M‐eigenvalue of a fourth‐order tensor. To solve the problem, we propose a practical method whose validity is guaranteed theoretically. To make the sequence generated by the method converge to a good solution of the problem, we also develop an initialization scheme. The given numerical experiments show the effectiveness of the proposed method. Copyright © 2009 John Wiley & Sons, Ltd.     

Local and parallel finite element algorithms for the Steklov eigenvalue problem

Based on the work of Xu and Zhou [Math Comput 69 (2000) 881–909], we propose and analyze in this article local and parallel finite element algorithms for the Steklov eigenvalue problem. We also prove a local error estimate which is suitable for the case that the locally refined region contains singular points lying on the boundary of domain, which is an improvement of the existing results. Numerical experiments are reported finally to validate our theoretical analysis. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 399–417, 2016     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Direct algorithms to solve the two‐sided obstacle problem for an M‐matrix

In this paper, two direct algorithms for solving the two‐sided obstacle problem with an M‐matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd.     

Two‐level additive Schwarz algorithms for nonlinear complementarity problem with an M‐function

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two‐level additive Schwarz algorithms for NCPs with an M‐function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd.     

Quasi‐optimality of the adaptive finite element method for the eigenvalue problem arising from the vibration frequencies of the cavity flow

In this article, we present a posteriori error analysis for the regularization formulation of the eigenvalue problem arising from the vibration frequencies of the cavity flow. The quasi‐optimality of the adaptive finite element method is also proved for the single eigenvalues under the Dörfler's marking strategy without marking the oscillation terms and enforcing the so‐called interior node property. Numerical examples illustrate the quasi‐optimality of the adaptive finite element method. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 900–922, 2015     

An inverse problem for an integro‐differential operator on a star‐shaped graph

A partial inverse problem for an integro‐differential Sturm‐Liouville operator on a star‐shaped graph is studied. We suppose that the convolution kernels are known on all the edges of the graph except one and recover the kernel on the remaining edge from a part of the spectrum. We prove the uniqueness theorem for this problem and develop a constructive algorithm for its solution, based on the reduction of the inverse problem on the graph to the inverse problem on the interval by using the Riesz basis property of the special system of functions.     

Projected Schur complement method for solving non‐symmetric systems arising from a smooth fictitious domain approach

This paper deals with a fast method for solving large‐scale algebraic saddle‐point systems arising from fictitious domain formulations of elliptic boundary value problems. A new variant of the fictitious domain approach is analyzed. Boundary conditions are enforced by control variables introduced on an auxiliary boundary located outside the original domain. This approach has a significantly higher convergence rate; however, the algebraic systems resulting from finite element discretizations are typically non‐symmetric. The presented method is based on the Schur complement reduction. If the stiffness matrix is singular, the reduced system can be formulated again as another saddle‐point problem. Its modification by orthogonal projectors leads to an equation that can be efficiently solved using a projected Krylov subspace method for non‐symmetric operators. For this purpose, the projected variant of the BiCGSTAB algorithm is derived from the non‐projected one. The behavior of the method is illustrated by examples, in which the BiCGSTAB iterations are accelerated by a multigrid strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

Local and parallel finite element method for solving the biharmonic eigenvalue problem of plate vibration

In this paper, we establish a new local and parallel finite element discrete scheme based on the shifted‐inverse power method for solving the biharmonic eigenvalue problem of plate vibration. We prove the local error estimation of finite element solution for the biharmonic equation/eigenvalue problem and prove the error estimation of approximate solution obtained by the local and parallel scheme. When the diameters of three grids satisfy H⁴ = ?(w²) = ?(h), the approximate solutions obtained by our schemes can achieve the asymptotically optimal accuracy. The numerical experiments show that the computational schemes proposed in this paper are effective to solve the biharmonic eigenvalue problem of plate vibration.     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Lorenz‐gauged vector potential formulations for the time‐harmonic eddy‐current problem with L∞‐regularity of material properties

In this paper, we consider some Lorenz‐gauged vector potential formulations of the eddy‐current problem for the time‐harmonic Maxwell equations with material properties having only L^∞‐regularity. We prove that there exists a unique solution of these problems, and we show the convergence of a suitable finite element approximation scheme. Moreover, we show that some previously proposed Lorenz‐gauged formulations are indeed formulations in terms of the modified magnetic vector potential, for which the electric scalar potential is vanishing. Copyright © 2007 John Wiley & Sons, Ltd.