1,721,198 research outputs found
Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form
No full textOrthogonal rational functions and diagonal-plus-semiseparable matrices
No full textThe space of all proper rational functions with prescribed real poles is considered. Given a set of points zi on the real line and the weights wi, we define the discrete inner product &lt,φ,ψ> := Σni=o wi2φ(zi)ψ(zi). In this paper we derive an efficient method to compute the coefficients of a recurrence relation generating a set of orthonormal rational basis functions with respect to the discrete inner product. We will show that these coefficients can be computed by solving an inverse eigenvalue problem for a diagonal-plus-semiseparable matrix
Het oplossen van veeltermsystemen
No full textSystems of polynomial equations arise naturally from many problems in applied mathematics and engineering. Examples of such problems come from robotics, chemical engineering, computer vision, dynamical systems theory, signal processing and geometric modeling, among others. The numerical solution of systems of polynomial equations is considered a challenging problem in computational mathematics. Important classes of existing methods are algebraic methods, which solve the problem using eigenvalue computations, and homotopy methods, which track solution paths in a continuous deformation of the system. In this text, we propose new algorithms of both these types which address some of the most important (numerical) shortcomings of existing methods.
Classical examples of algebraic techniques use Gröbner bases, border bases or resultants. These methods take advantage of the fact that the solutions are encoded by the structure of an algebra that is naturally defined by the equations of the system. In order to do computations in this algebra, the algorithms choose a representation of it which is usually given by a set of monomials satisfying some conditions. In this thesis we show that these conditions are often too restrictive and may lead to severe numerical instability of the algorithms. This results in the fact that they are not feasible for finite precision arithmetic. We propose the framework of truncated normal forms to remedy this and develop new, robust and stabilized methods. The framework generalizes Gröbner and border bases as well as some resultant based algorithms. We present explicit constructions for square systems which show `generic' behavior with respect to the Bézout root count in affine space or the Bernstein-Khovanskii-Kushnirenko root count in the algebraic torus. We show how the presented techniques can be used in a homogeneous context by introducing homogeneous normal forms, which offer an elegant way of dealing with solutions `at infinity'. For instance, homogeneous normal forms can be used to solve systems which define finitely many solutions in projective space by working in its graded, homogeneous coordinate ring. We develop the necessary theory for generalizing this approach to the homogeneous coordinate ring (or Cox ring) of compact toric varieties. In this way we obtain an algorithm for solving systems on a compactification of the algebraic torus which takes the polyhedral structure of the equations into account. This approach is especially effective in the case where the system defines solutions on or near the boundary of the torus in its compactification, which typically causes difficulties for other solvers. Each of the proposed methods is tested extensively in numerical experiments and compared to existing implementations.
Homotopy methods are perhaps the most popular methods for the numerical solution of systems of polynomial equations. One of the reasons is that, in general, their computational complexity scales much better with the number of variables in the system than that of algebraic methods. However, the reliability of these methods depends strongly on some design choices in the algorithm. An important example is the choice of step size in the discretization of the solution paths. Choosing this too small leads to a large computational cost and prohibitively long computation times, while choosing it too large may lead to path jumping, which is a typical cause for missing solutions in the output of a homotopy algorithm. In this thesis, a new adaptive step size path tracking algorithm is proposed which is shown to be much less prone to path jumping than the state of the art software.status: Publishe
Diagonal-Plus-Semiseparable Matrices and Their Use in Numerical Linear Algebra
No full textGestructureerde matrices zijn zeer belangrijk in lineaire algebra omdat ze minder geheugenplaats innemen dan algemene matrices en omdat bewerkingen met deze matrices minder rekenwerk vergen dan wanneer volle, niet-gestructureerde matrices gebruikt worden. Diagonaal-plus-semiseparabele matrices vormen een klasse van zulke gestructureerde matrices. In dit proefschrift zoeken we naar een geschikte definitie voor deze klasse van matrices en een bijpassende voorstelling. Ook andere definities die in de literatuur gebruikt worden, worden belicht en de studie van diagonaal-plus-semiseparabele matrices wordt gemotiveerd. In een eerste deel construeren we een reductie algoritme dat elke symmetrische matrix omzet in een overeenkomstige diagonaal-plus-semiseparabele matrix. Dit algoritme heeft het Lanczos-Ritz convergentiegedrag en in elke stap wordt er een geneste deelruimte iteratie uitgevoerd. Deel 2 belicht twee basisproblemen uit numerieke lineaire algebra: het oplossen van lineaire systemen en het symmetrisch eigenwaardeprobleem. Eerst construeren we twee snelle algoritmes om diagonaal-plus-semiseparabele lineaire systemen op te lossen. Daarna bespreken we drie verschillende technieken die gebruikt worden om het symmetrisch eigenwaardeprobleem op te lossen voor diagonaal-plus-semiseparabele matrices: een impliciet QR-algoritme, drie verschillende verdeel-en-heers algoritmes en een Cholesky-LR-algoritme. Het laatste algoritme is enkel toepasbaar op symmetrische, positief definiete diagonaal-plus-semiseparabele matrices. In het laatste deel introduceren we twee hogere rang uitbreidingen van semiseparabele matrices samen met een bijpassende voorstelling. Elke symmetrische matrix kan omgezet worden in een overeenkomstige hogere rang semiseparabele matrix en deze omzetting heeft het blok-Lanczos-Ritz convergentiegedrag gecombineerd met een soort van geneste deelruimte iteratie in elke stap. Numerieke experimenten zijn toegevoegd en de programma's zijn ter beschi kking gesteld op het internet.status: Publishe
Orthogonale veeltermen en matrices. Toepassingen van recursie betrekkingen.
No full textUnivariate and multivariate polynomials play a fundamental role in pure and applied mathematics.
In this text orthogonal polynomials and their corresponding recurrence relations are studied
and connected to matrix computations
and applied in polynomial interpolation and approximation and in polynomial system solving.
For univariate orthogonal polynomials on the complex unit circle, efficient algorithms for the
Geronimus transformation are designed and their accuracy is discussed based on several numerical
experiments. The Uvarov transformation depends on a parameter . The values of for which
the Uvarov transformation maintains the positive definiteness of the original bilinar functional
are determined. Exploiting the correspondence between -unitary Hessenberg matrices and
quasi-definite functionals on the unit circle, a QR algorithm is developed for this type of matrices.
For multivariate orthogonal polynomials with respect to a discrete inner product, a framework is presented that connects monomial orders, the structure of the corresponding recurrence matrices, the discrete inner product and the related inverse eigenvalue problem. Results are given concerning the algorithms to solve this inverse eigenvalue problem, the uniqueness of the solution and the multivariate vector monomial orders that can be used.
As an application several algorithms are designed to compute point configurations for multivariate polynomial interpolation and least squares approximation that have a low or even almost minimal Lebesgue constant for a given geometry.
The polynomial functions are represented using orthogonal bases with respect to
a discrete inner product where the mass points are lying within the considered geometry.
As another application, a generalized companion method to solve systems of polynomials is developed.
The matrices of the generalized eigenvalue problem are sparse and structured and they contain the coefficients of recurrence relations of the multivariate basis polynomials and the coefficients of the system of polynomial equations.status: Publishe
Eigenvalues, Orthogonal Functions and Structured Matrices
No full textIn this thesis eigenvalues, structured matrices and orthogonal functions are studied from a practical point of view. In general, we try to exploit relations between any of these three concepts to design algorithms in the context of five problems. Each problem is closely related to one of the basic linear algebra problems: solving a system of linear equations or an eigenvalue problem.Firstly, we study a problem arising from graph theory. There are different ways to map graphs to structured matrices, and depending on the matrix different graph-theoretic properties can be derived from their eigenvalues. An open question whether the regularity of a graph could or could not be derived from the spectrum of a certain class of structured matrices is solved. The second aspect of the present thesis relates to a common method for eigenvalue computation, namely, a rational Lanczos method. Close relation between this algorithm and a certain minimization problem for orthogonal rational functions gives a possibility for numerical exploration of convergence properties of the algorithm without running it. Such exploration is reduced to solving a constrained weighted energy problem from logarithmic potential theory, which, in its turn, is converted to a linear system. The focus lies on this convergence exploration method.Then a method to compute recurrence relation coefficients for bivariate polynomials, orthonormal with respect to a discrete inner product, is studied. To compute these polynomials, the inverse eigenvalue problem is posed and solved efficiently and in a stable way. This is achieved by applying Givens rotations to certain structured matrices and yields the generalized Hessenberg matrices, containing the recurrence relation coefficients.Finally, several linear-algebraic problems with structured matrices are studied with a continuation method. Such a method defines an easy problem with a known solution and a path between this problem and the one we are wishing to solve. Instead of solving the target problem directly, the solution to the easy one is gradually transformed to the desired one. With this approach we first solve a linear system of equations with Toeplitz coefficient matrix, and later we find all the eigenvalues and eigenvectors of a symmetric diagonal-plus-semiseparable matrix. Both types of structured matrices exhibit close relation with certain classes of orthogonal functions.Numerical experiments are included for all the proposed methods and illustrate the stability and accuracy of the methods.status: Publishe
Korte recursie relaties voor (uitgebreide) Krylov ruimten
No full textBoth Krylov and extended Krylov subspaces are used for numerous purposes, such as solving linear systems of equations, iterative methods for finding eigenvalues, and computation of matrix functions. For numerical reasons, it is most convenient to represent these subspaces as the span of a set of orthonormal basis vectors. We focus on the computation of these basis vectors.
In general, orthonormal bases for an (extended) Krylov subspace are computed by means of so-called recurrence relations, which express a recursive link between the orthonormal vectors. The smaller the number of terms in this recurrence relation, the less computational effort is needed to find an orthonormal basis for the considered subspace. The structure of the recurrence relation is reflected in that of the so-called recurrence matrix, which is the matrix representation of the investigated linear operator with respect to the orthonormal basis.
There are two sources of structure that arise in the matrix representation of a linear operator with respect to an orthonormal basis. The first originates from the choice of subspace with respect to which the matrix representation is generated: a Krylov subspace imposes a Hessenberg structure on the matrix representation of the operator, while an extended Krylov subspace imposes a so-called extended Hessenberg structure on the matrix representation of the operator. The second is due to any structure inherent in the linear operator itself. For example, the matrix representation of an Hermitian operator with respect to an orthonormal basis of a Krylov subspace is tridiagonal. The recurrence matrix will be studied for several matrix classes along with the accompanying recurrence relations.
For the classical Krylov case, specific attention is paid to the class of matrices whose adjoint is a low rank perturbation of a low degree rational function in the matrix. This class of matrices, which we will refer to as BML-matrices, gives rise to a low rank structure in the recurrence matrix. In our analysis, a connection between this low rank part and GMRES residual vectors will come about, engendering the design of a new economical Arnoldi iteration.
For the extended Krylov case, specific attention is paid to the class of unitary and Hermitian matrices. For the class of Hermitian matrices, some known results in the literature are placed in a broader perspective, with which the structure of the recurrence matrix can be predicted elegantly and from which a corresponding algorithm can be derived. For the class of unitary matrices, coupled recurrence relations are derived which form the basis of an algorithm that returns a sparse factorization of the recurrence matrix.status: Publishe
- …
