Search

When exploring the literature, it can be observed that the operator obtained when applying Newton-like root finding algorithms to the quadratic polynomials z2 − c has the same form regardless of which algorithm has been used. In this paper, we justify why this expression is obtained. This is done by studying the symmetries of the operators obtained after applying Newton-like algorithms to a family of degree d polynomials p(z) = zd − c. Moreover, we provide an iterative procedure to obtain the expression of new Newton-like algorithms. We also carry out a dynamical study of the given generic operator and provide general conclusions of this type of methods. [ABSTRACT FROM AUTHOR]

Theory of quasi-orthogonal polynomials is significantly related to constructing vector Padé approximations. The present paper introduces an efficient procedure to compute adjacent families of quasi-orthogonal polynomials as defined in Sadaka (Appl. Numer. Math. 21:57–70, 1996) and Sadaka (Appl. Numer. Math. 24:483–499, 1997). The derived algorithm uses short recursive relations whose coefficients are written in terms of lower triangular block determinants. The strategy of computing such determinants is given and analyzed. [ABSTRACT FROM AUTHOR]

In this paper, novel representations of generalized inverses of rational matrices are developed. Therefore, a unified approach for the computation of {1,2,3} and {1,2,4} inverses and Moore-Penrose inverse of a given matrix A is considered. Full-rank QDR decomposition of a rational matrix is utilized to avoid the square roots of rational expressions in the evaluations, making the given algorithm very suitable for symbolic computations of generalized matrix inverses. Furthermore, we developed an algorithm for symbolic computation of the Moore-Penrose inverse of a polynomial matrix using the full-rank QDR decomposition, therefore maximizing the potential of using square root–free polynomial entries. Introduced algorithms are illustrated via numerical examples. [ABSTRACT FROM AUTHOR]

Since the beginning of the development of interior-point methods, there exists a puzzling gap between the results in theory and the observations in numerical experience, i.e., algorithms with good polynomial bounds are not computationally efficient and algorithms demonstrated efficiency in computation do not have a good or any polynomial bound. Todd raised a question in 2002: “Can we find a theoretically and practically efficient way to reoptimize?” This paper is an effort to close the gap. We propose two arc-search infeasible interior-point algorithms with infeasible central path neighborhood wider than all existing infeasible interior-point algorithms that are proved to be convergent. We show that the first algorithm is polynomial and its simplified version has a complexity bound equal to the best known complexity bound for all (feasible or infeasible) interior-point algorithms. We demonstrate the computational efficiency of the proposed algorithms by testing all Netlib linear programming problems in standard form and comparing the numerical results to those obtained by Mehrotra’s predictor-corrector algorithm and a recently developed more efficient arc-search algorithm (the convergence of these two algorithms is unknown). We conclude that the newly proposed algorithms are not only polynomial but also computationally competitive compared to both Mehrotra’s predictor-corrector algorithm and the efficient arc-search algorithm. [ABSTRACT FROM AUTHOR]

In this paper we present a new algorithm for solving polynomial equations based on the Taylor series of the inverse function of a polynomial, f( y). The foundations of the computing of such series have been previously developed by the authors in some recent papers, proceeding as follows: given a polynomial function $y=P(x)=a_0+a_1x+\cdots+a_mx^m$, with $a_i \in \mathcal{R}, 0 \leq i \leq m$, and a real number u so that P′( u) ≠ 0, we have got an analytic function f( y) that satisfies x = f( P( x)) around x = u. Besides, we also introduce a new proof (completely different) of the theorems involves in the construction of f( y), which provide a better radius of convergence of its Taylor series, and a more general perspective that could allow its application to other kinds of equations, not only polynomials. Finally, we illustrate with some examples how f( y) could be used for solving polynomial systems. This question has been already treated by the authors in preceding works in a very complex and hard way, that we want to overcome by using the introduced algorithm in this paper. [ABSTRACT FROM AUTHOR]

In the present paper we introduce new matrix extrapolation methods as generalizations of well known methods such as polynomial vector extrapolation methods or 휖-type algorithms. We give expressions of the obtained approximations via the Schur complement, the Kronecker product and also by using a new matrix product. We apply these methods to linearly generated sequences especially those arising in control or in ill-posed problems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate variants of the well-known Golub and Welsch algorithm for computing nodes and weights of Gaussian quadrature rules for symmetric weights w in intervals (− a, a) (not necessarily bounded). The purpose is to reduce the complexity of the Jacobi eigenvalue problem stemming from Wilf's theorem and show the effectiveness of Matlab implementations of our variants for reducing the computer times compared to some other methods. Numerical examples on three test problems show the benefits of these variants. [ABSTRACT FROM AUTHOR]

The Bernstein operators of second kind were introduced by Paolo Soardi in 1990, in terms of a random walk on a certain hypergroup. They have the same relation with Chebyshev polynomials of second kind as the classical Bernstein operators have with Chebyshev polynomials of first kind. In this paper we describe a de Casteljau type algorithm for these operators. [ABSTRACT FROM AUTHOR]

In this paper an interior-point algorithm for P( κ) horizontal linear complementarity problems is proposed that uses new search directions. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has quadratically convergent with polynomial iteration complexity $O((1+\kappa)\sqrt{n}\log\frac{n}{\varepsilon})$, coincide with the best known iteration bound for P( κ) horizontal linear complementarity problems. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for computing the roots of a monic matrix polynomial. To this end we compute the eigenvalues of the corresponding block companion matrix C. This is done by implementing the QR algorithm in such a way that it exploits the rank structure of the matrix. Because of this structure, we can represent the matrix in Givens-weight representation. A similar method as in Chandrasekaran et al. (Oper Theory Adv Appl 179:111-143, ), the bulge chasing, is used during the QR iteration. For practical usage, matrix C has to be brought in Hessenberg form before the QR iteration starts. During the QR iteration and the transformation to Hessenberg form, the property of the matrix being unitary plus low rank numerically deteriorates. A method to restore this property is used. [ABSTRACT FROM AUTHOR]

Interior-point methods for semidefinite optimization problems have been studied frequently, due to their polynomial complexity and practical implications. In this paper we propose a primal-dual infeasible interior-point algorithm that uses full Nesterov-Todd (NT) steps with a different feasibility step. We obtain the currently best known iteration bound for semidefinite optimization problems. [ABSTRACT FROM AUTHOR]

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base 2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets. [ABSTRACT FROM AUTHOR]

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods. [ABSTRACT FROM AUTHOR]

In this paper, we present new approaches computing the rank and the null space of the ( m n + p)×( n + p) generalized Sylvester matrix of ( m + 1) polynomials of maximal degrees n, p. We introduce an algorithm which handles directly a modification of the generalized Sylvester matrix, computing efficiently its rank and null space and replacing n by log2 n in the required complexity of the classical methods. We propose also a modification of the Gauss-Jordan factorization method applied to the appropriately modified Sylvester matrix of two polynomials for computing simultaneously its rank and null space. The methods can work numerically and symbolically as well and are compared in respect of their error analysis, complexity and efficiency. Applications where the computation of the null space of the generalized Sylvester matrix is required, are also given. [ABSTRACT FROM AUTHOR]

It is well known that it is an ill-posed problem to decide whether a function has a multiple root. Even for a univariate polynomial an arbitrary small perturbation of a polynomial coefficient may change the answer from yes to no. Let a system of nonlinear equations be given. In this paper we describe an algorithm for computing verified and narrow error bounds with the property that a slightly perturbed system is proved to have a double root within the computed bounds. For a univariate nonlinear function f we give a similar method also for a multiple root. A narrow error bound for the perturbation is computed as well. Computational results for systems with up to 1000 unknowns demonstrate the performance of the methods. [ABSTRACT FROM AUTHOR]

A monic Jacobi matrix is a tridiagonal matrix which contains the parameters of the three-term recurrence relation satisfied by the sequence of monic polynomials orthogonal with respect to a measure. The basic Geronimus transformation with shift α transforms the monic Jacobi matrix associated with a measure dμ into the monic Jacobi matrix associated with dμ/( x − α) + Cδ( x − α), for some constant C. In this paper we examine the algorithms available to compute this transformation and we propose a more accurate algorithm, estimate its forward errors, and prove that it is forward stable. In particular, we show that for C = 0 the problem is very ill-conditioned, and we present a new algorithm that uses extended precision. [ABSTRACT FROM AUTHOR]