Pythagorean-hodograph space curves

We investigate the properties of polynomial space curvesr(t)={x(t), y(t), z(t)} whose hodographs (derivatives) satisfy the Pythagorean conditionx′²(t)+y′²(t)+z′²(t)≡σ²(t) for some real polynomial σ(t). The algebraic structure of thecomplete set of regular Pythagorean-hodograph curves in ℝ³ is inherently more complicated than that of the corresponding set in ℝ². We derive a characterization for allcubic Pythagoreanhodograph space curves, in terms of constraints on the Bézier control polygon, and show that such curves correspond geometrically to a family of non-circular helices. Pythagorean-hodograph space curves of higher degree exhibit greater shape flexibility (the quintics, for example, satisfy the general first-order Hermite interpolation problem in ℝ³), but they have no “simple” all-encompassing characterization. We focus on asubset of these higher-order curves that admits a straightforward constructive representation. As distinct from polynomial space curves in general, Pythagorean-hodograph space curves have the following attractive attributes: (i) the arc length of any segment can be determined exactly without numerical quadrature; and (ii) thecanal surfaces based on such curves as spines have precise rational parameterizations.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

Error estimates for finite element approximations of nonlinear monotone elliptic problems with application to numerical homogenization

We consider a finite element method (FEM) with arbitrary polynomial degree for nonlinear monotone elliptic problems. Using a linear elliptic projection, we first give a new short proof of the optimal convergence rate of the FEM in the L² norm. We then derive optimal a priori error estimates in the H¹ and L² norm for a FEM with variational crimes due to numerical integration. As an application, we derive a priori error estimates for a numerical homogenization method applied to nonlinear monotone elliptic problems. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 955–969, 2016     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

Spectral collocation methods for nonlinear weakly singular Volterra integro‐differential equations

In this paper, a spectral collocation approximation is proposed for neutral and nonlinear weakly singular Volterra integro‐differential equations (VIDEs) with non‐smooth solutions. We use some suitable variable transformations to change the original equation into a new equation, so that the solution of the resulting equation possesses better regularity, and the the Jacobi orthogonal polynomial theory can be applied conveniently. Under reasonable assumptions on the nonlinearity, we carry out a rigorous error analysis in L^∞ norm and weighted L² norm. To perform the numerical simulations, some test examples (linear and nonlinear) are considered with nonsmooth solutions, and numerical results are presented. Further more, the comparative study of the proposed methods with some existing numerical methods is provided.     

An h–p version of the Chebyshev spectral collocation method for nonlinear delay differential equations

We develop and analyze a spectral collocation method based on the Chebyshev–Gauss–Lobatto points for nonlinear delay differential equations with vanishing delays. We derive an a priori error estimate in the H¹‐norm that is completely explicit with respect to the local time steps and the local polynomial degrees. Several numerical examples are provided to illustrate the theoretical results.     

The Distribution of Condition Numbers of Rational Data of Bounded Bit Length

We prove that rational data of bounded input length are uniformly distributed (in the classical sense of H. Weyl, in [42]) with respect to the probability distribution of condition numbers of numerical analysis. We deal both with condition numbers of linear algebra and with condition numbers for systems of multivariate polynomial equations. For instance, we prove that for a randomly chosen n\times n rational matrix M of bit length O(n ⁴ log n) + log w , the condition number k(M) satisfies k(M) ≤ w n ^5/2 with probability at least 1-2w ^-1 . Similar estimates are established for the condition number μ_ norm of M. Shub and S. Smale when applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, we apply these techniques to estimate the probability distribution of the precision (number of bits of the denominator) required to write approximate zeros of systems of multivariate polynomial equations of bounded input length. March 7, 2001. Final version received: June 7, 2001.     

A construction of polynomial lattice rules with small gain coefficients

In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of N ^{−(2α+1)+δ} , for all δ > 0, assuming that the function under consideration has bounded variation of order α for some 0 < α ≤ 1, and where N denotes the number of quadrature points. An analogous result is obtained for Korobov polynomial lattice rules. It is also established that these rules are almost optimal for the function space considered in this paper. Furthermore, we discuss the implementation of the component-by-component approach and show how to reduce the computational cost associated with it. Finally, we present numerical results comparing scrambled polynomial lattice rules and scrambled digital nets.     

Explicit polynomial preserving trace liftings on a triangle

We give an explicit formula for a right inverse of the trace operator from the Sobolev space H¹(T) on a triangle T to the trace space H^1/2(?T) on the boundary. The lifting preserves polynomials in the sense that if the boundary data are piecewise polynomial of degree N, then the lifting is a polynomial of total degree at most N and the lifting is shown to be uniformly stable independently of the polynomial order. Moreover, the same operator is shown to provide a uniformly stable lifting from L₂(?T) to H^1/2(T). Finally, the lifting is used to construct a uniformly bounded right inverse for the normal trace operator from the space H (div; T) to H^–1/2(?T) which also preserves polynomials. Applications to the analysis of high order numerical methods for partial differential equations are indicated (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The modified bordering method to evaluate eigenvalues and eigenvectors of normal matrices

A bordering procedure is here proposed to evaluate the eigensystem of hermitian matrices, and more in general of normal matrices, when the spectral decomposition is known of then–1×n–1 principal minor. The procedure is also applicable to special real and nonsymmetric matrices here named quasi-symmetric. The computational cost to write the characteristic polynomial isO(n ²), using a new set of recursive formulas. A modified Brent algorithm is used to find the roots of the polynomial. The eigenvectors are evaluated in a direct way with a computational cost ofO(n ²) for each one. Some numerical considerations indicate where numerical difficulties may occur. Numerical results are given comparing this method with the Givens-Householder one.     

A numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

Finite element method for Grwünwald–Letnikov time-fractional partial differential equation

In this article, we consider the finite element methods (FEM) for Grwünwald–Letnikov time-fractional diffusion equation, which is obtained from the standard two-dimensional diffusion equation by replacing the first-order time derivative with a fractional derivative (of order α, with 0?h ^r+1?+?τ^2-α), where h, τ and r are the space step size, time step size and polynomial degree, respectively. A numerical example is presented to verify the order of convergence.     

An Adaptive CGNR Algorithm for Solving Large Linear Systems

In this paper, an adaptive algorithm based on the normal equations for solving large nonsymmetric linear systems is presented. The new algorithm is a hybrid method combining polynomial preconditioning with the CGNR method. Residual polynomial is used in the preconditioning to estimate the eigenvalues of the s.p.d. matrix A ^T A, and the residual polynomial is generated from several steps of CGNR by recurrence. The algorithm is adaptive during its implementation. The robustness is maintained, and the iteration convergence is speeded up. A numerical test result is also reported.     

Numerical integration with polynomial exactness over a spherical cap

This paper presents rules for numerical integration over spherical caps and discusses their properties. For a spherical cap on the unit sphere \mathbbS²\mathbb{S}^2, we discuss tensor product rules with n ²/2 + O(n) nodes in the cap, positive weights, which are exact for all spherical polynomials of degree ≤ n, and can be easily and inexpensively implemented. Numerical tests illustrate the performance of these rules. A similar derivation establishes the existence of equal weight rules with degree of polynomial exactness n and O(n ³) nodes for numerical integration over spherical caps on \mathbbS²\mathbb{S}^2. For arbitrary d ≥ 2, this strategy is extended to provide rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that have O(n ^d ) nodes in the cap, positive weights, and are exact for all spherical polynomials of degree ≤ n. We also show that positive weight rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that are exact for all spherical polynomials of degree ≤ n have at least O(n ^d ) nodes and possess a certain regularity property.     

Polynomial numerical hulls of matrix polynomials,II

In this article, we study some algebraic and geometrical properties of polynomial numerical hulls of matrix polynomials and joint polynomial numerical hulls of a finite family of matrices (possibly the coefficients of a matrix polynomial). Also, we study polynomial numerical hulls of basic A-factor block circulant matrices. These are block companion matrices of particular simple monic matrix polynomials. By studying the polynomial numerical hulls of the Kronecker product of two matrices, we characterize the polynomial numerical hulls of unitary basic A-factor block circulant matrices.     

The Virtual Poincaré Polynomials of Homogeneous Spaces

We factor the virtual Poincaré polynomial of every homogeneous space G/H, where G is a complex connected linear algebraic group and H is an algebraic subgroup, as t^2u (t²–1)^r Q_G/H(t²) for a polynomial Q_G/H with nonnegative integer coefficients. Moreover, we show that Q_G/H(t²) divides the virtual Poincaré polynomial of every regular embedding of G/H, if H is connected.     

On regular polynomial endomorphisms of ℂ<Superscript>2</Superscript> without bounded critical orbitswithout bounded critical orbits

We study conditions involving the critical set of a regular polynomial endomorphism f∶ℂ²↦ℂ² under which all complete external rays from infinity for f have well defined endpoints.     

BiCGstab(l) and other hybrid Bi-CG methods

It is well-known that Bi-CG can be adapted so that the operations withA ^T can be avoided, and hybrid methods can be constructed in which it is attempted to further improve the convergence behaviour. Examples of this are CGS, Bi-CGSTAB, and the more general BiCGstab(l) method. In this paper it is shown that BiCGstab(l) can be implemented in different ways. Each of the suggested approaches has its own advantages and disadvantages. Our implementations allow for combinations of Bi-CG with arbitrary polynomial methods. The choice for a specific implementation can also be made for reasons of numerical stability. This aspect receives much attention. Various effects have been illustrated by numerical examples.     

A compound matrix algorithm for the computation of the Smith form of a polynomial matrix

In the present paper is presented a numerical method for the exact reduction of a singlevariable polynomial matrix to its Smith form without finding roots and without applying unimodular transformations. Using the notion of compound matrices, the Smith canonical form of a polynomial matrixM(s)^nxn[s] is calculated directly from its definition, requiring only the construction of all thep-compound matricesC _p (M(s)) ofM(s), 1<pn. This technique produces a stable and accurate numerical algorithm working satisfactorily for any polynomial matrix of any degree.     

Polynomial growth rates

We consider linear equations v^′=A(t)v with a polynomial asymptotic behavior, that can be stable, unstable and central. We show that this behavior is exhibited by a large class of differential equations, by giving necessary and sufficient conditions in terms of generalized “polynomial” Lyapunov exponents for the existence of polynomial behavior. In particular, any linear equation in block form in a finite-dimensional space, with three blocks having “polynomial” Lyapunov exponents respectively negative, positive, and zero, has a nonuniform version of polynomial trichotomy, which corresponds to the usual notion of trichotomy but now with polynomial growth rates. We also obtain sharp bounds for the constants in the notion of polynomial trichotomy. In addition, we establish the persistence under sufficiently small nonlinear perturbations of the stability of a nonuniform polynomial contraction.