Perturbation and error analyses for block downdating of a Cholesky decomposition

A new perturbation result is presented for the problem of block downdating a Cholesky decompositionX ^T X = R ^T R. Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations. An error analysis is also given for block downdating using Corrected Seminormal Equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations. We classify the problems for which the CSNE downdating method produces a downdated upper triangular matrix which is comparable in accuracy to the upper triangular factor obtained from the QR decomposition by Householder transformations on the data matrix with the row block deleted.Dedicated to Ji-guang Sun in honour of his 60th birthdayThe work of the second author was supported in part by the National Science Foundation grant CCR-9209726.     

Accurate downdating of a modified Gram-Schmidt QR decomposition

A new algorithm for downdating a QR decomposition is presented. We show that, when the columns in the Q factor from the Modified Gram-Schmidt QR decomposition of a matrixX are exactly orthonormal, the Gram-Schmidt downdating algorithm for the QR decomposition ofX is equivalent to downdating the full Householder QR decomposition of the matrixX augmented by ann ×n zero matrix on top. Using this relation, we derive an algorithm that improves the Gram-Schmidt downdating algorithm when the columns in the Q factor are not orthonormal. Numerical test results show that the new algorithm produces far more accurate results than the Gram-Schmidt downdating algorithm for certain ill-conditioned problems.This work was partially supported in part by the National Science Foundation grants CCR-9209726 and CCR-9509085.     

Fast Algorithm for Cross-Validation of the Best Linear Unbiased Predictor

This article proposes a new algorithm for cross-validation of the best linear unbiased predictor. The algorithm relies on a new technique for downdating the inverse of a Cholesky factor. Given n data points, the new algorithm has complexity O(n³), compared to O(n⁴), which is the order for the more traditional delete one and recalculate method.     

Metrica hermitiana ellittica in uno spazio proiettivo quaternionale

Riassunto Si definisce e si studia una nozione di distanza nello spazio proiettivo q aternionaleT _n ^Q , la quale si riduce nell'infinitesimo alla meirica riemanniana del modello metrico reale diT _n ^Q assegnato daMartinelli, e subordina le nozioni di distanza diCayley-Klein e diFubini-Study negli spazi proiettivi reale e complessoT _n ^R ,T _n ^C subordinati aT _n ^Q . A M. Enrico Bompiani nel suo giubileo scientifico Lavoro eseguito nell'ambito del Gruppo di ricerca n. 37 del C. N. R.     

A stationary iterative pseudoinverse algorithm

Iterative methods applied to the normal equationsA ^T Ax=A ^T b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent system. This work was supported by the Swedish Research Council for Engineering Sciences, TFR.     

Stability analysis of a general toeplitz systems solver

We show that a fast algorithm for theQR factorization of a Toeplitz or Hankel matrixA is weakly stable in the sense thatR ^T R is close toA ^T A. Thus, when the algorithm is used to solve the semi-normal equationsR ^TRx=A^T b, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear systemAx=b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem min ||Ax-b||₂.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

Amalgamation bases for commutative rings without nilpotent elements

SCR=the class of commutative rings without nilpotent elements.Theorem,R is an amalgamation base for SCR iff rad (I=Ann²(I) forI ⊆R finitely generated. Supplement. IfR ε SCR thenR is contained in an amalgamation basis for SCR having no new idempotent elements. CR=the class of commutative rings. Theorem.R is an amalgamation base for CR iffR is a pureR-submodule of any commutative ring extendingR.     

On accelerating PL continuation algorithms by predictor—corrector methods

We consider path following methods designed to trace the zeroes of a continuous or differentiable mapF:R ⁿ⁺¹ R ⁿ . These methods are applicable e.g. in the numerical study of nonlinear eigenvalue and bifurcation problems. Traditionally a simplicial algorithm is based on a fixed triangulationT ofR ⁿ⁺¹ and a corresponding piecewise linear approximationF _T :R ⁿ⁺¹ R ⁿ .4 A fixed triangulation algorithm then traces the zeroes ofF _T via a complementary pivoting procedure. We present two kinds of hybrid algorithms that have the structure of a predictor—corrector method using simplicial methods to carry out the corrector steps. Numerical experience is reported showing the improvement in efficiency as compared to the fixed triangulation algorithm.     

On acceleration methods for coupled nonlinear elliptic systems

Summary We compare both numerically and theoretically three techniques for accelerating the convergence of a nonlinear fixed point iterationuT(u), arising from a coupled elliptic system: Chebyshev acceleration, a second order stationary method, and a nonlinear version of the Generalized Minimal Residual Algorithm (GMRES) which we call NLGMR. All three approaches are implemented in Jacobian-free mode, i.e., only a subroutine which returnsT(u) as a function ofu is required.We present a set of numerical comparisons for the drift-diffusion semiconductor model. For the mappingT which corresponds to the nonlinear block Gauß-Seidel algorithm for the solution of this nonlinear elliptic system, NLGMR is found to be superior to the second order stationary method and the Chebychev acceleration. We analyze the local convergence of the nonlinear iterations in terms of the spectrum [T _u (u ^(*))] of the derivativeT _u at the solutionu ^(*). The convergence of the original iteration is governed by the spectral radius [T _U (u ^(*))]. In contrast, the convergence of the two second order accelerations are related to the convex hull of [T _u (u ^(*))], while the convergence of the GMRES-based approach is related to the local clustering in [I–T _u (u ^(*))]. The spectrum [I–T _u (u ^(*))] clusters only at 1 due to the successive inversions of elliptic partial differential equations inT. We explain the observed superiority of GMRES over the second order acceleration by its ability to take advantage of this clustering feature, which is shared by similar coupled nonlinear elliptic systems.     

Matrices, moments and quadrature II; How to compute the norm of the error in iterative methods

In this paper, we study the numerical computation of the errors in linear systems when using iterative methods. This is done by using methods to obtain bounds or approximations of quadratic formsu ^T A ⁻¹ u whereA is a symmetric positive definite matrix andu is a given vector. Numerical examples are given for the Gauss-Seidel algorithm. Moreover, we show that using a formula for theA-norm of the error from Dahlquist, Golub and Nash [1978] very good bounds of the error can be computed almost for free during the iterations of the conjugate gradient method leading to a reliable stopping criterion. The work of the first author was partially supported by NSF Grant CCR-950539.     

Prime ideals in the C*-algebra of a nilpotent group

We say that a locally compact groupG hasT ₁ primitive ideal space if the groupC ^*-algebra,C ^*(G), has the property that every primitive ideal (i.e. kernel of an irreducible representation) is closed in the hull-kernel topology on the space of primitive ideals ofC ^*(G), denoted by PrimG. This means of course that every primitive ideal inC ^*(G) is maximal. Long agoDixmier proved that every connected nilpotent Lie group hasT ₁ primitive ideal space. More recentlyPoguntke showed that discrete nilpotent groups haveT ₁ primitive ideal space and a few month agoCarey andMoran proved the same property for second countable locally compact groups having a compactly generated open normal subgroup. In this note we combine the methods used in [3] with some ideas in [9] and show that for nilpotent locally compact groupsG, having a compactly generated open normal subgroup, closed prime ideals inC ^*(G) are always maximal which implies of course that PrimG isT ₁.     

Sobolev inner products and orthogonal polynomials of Sobolev type

This survey paper deals with polynomials which are orthogonal with respect to scalar products of the form _R F ^T[A]G withF ^T=[f(x), f(Ⅎ(x),...f ^(y)(x)], [A] A _ji =A _ji =A _ij =d _ji (I _ji ) where d _ji is a measure of supportI _ij and [A] is positive semi-definite. Basic properties are indicated or proved in particular cases.     

Convergence of the Dirichlet solutions of the very fast diffusion equation

For any −1<m<0, positive functions f, g and u₀≥0, we prove that under some mild conditions on f, g and u₀ as R→∞ the solution u^R of the Dirichlet problem u_t=(u^m/m)_xx in (−R,R)×(0,∞), u(R,t)=(f(t)|m|R)^1/m, u(−R,t)=(g(t)|m|R)^1/m for all t>0, u(x,0)=u₀(x) in (−R,R), converges uniformly on every compact subset of R×(0,T) to the solution of the equation u_t=(u^m/m)_xx in R×(0,T), u(x,0)=u₀(x) in R, which satisfies some mass loss formula on (0,T) where T is the maximal time such that the solution u is positive. We also prove that the solution constructed is equal to the solution constructed in Hui (2007) [15] using approximation by solutions of the corresponding Neumann problem in bounded cylindrical domains.     

On the algebra of quasi-shuffles

For any commutative algebra R the shuffle product on the tensor module T(R) can be deformed to a new product. It is called the quasi-shuffle algebra, or stuffle algebra, and denoted T ^q (R). We show that if R is the polynomial algebra, then T ^q (R) is free for some algebraic structure called Commutative TriDendriform (CTD-algebras). This result is part of a structure theorem for CTD-bialgebras which are associative as coalgebras and whose primitive part is commutative. In other words, there is a good triple of operads (As, CTD, Com) analogous to (Com, As, Lie). In the last part we give a similar interpretation of the quasi-shuffle algebra in the noncommutative setting.     

A note onR 1-topological spaces

The purpose of the present note is to give a number of characterizations of theR ₁-axiom and to show that theR ₁-axiom is equivalent to the weakly Hausdorff axiom introduced byB. Banaschewski andJ. M. Maranda [2]. In anR ₁-space it is shown that the locally compactness property is also open hereditary and that the closure of an almost compact set is the union of the closures of its points. A necessary and sufficient condition is obtained under which a locally compact set dense in anR ₁-space is open. Finally a variant of a well-known theorem regarding two continuous functions of a topological space into aT ₂-space is formulated forR ₁-spaces.     

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.     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

Convergence properties of ART and SOR algorithms

Summary ART algorithms with relaxation parameters are studied for general (consistent or inconsistent) linear algebraic systemsRx=f, and a general convergence theorem is formulated. The advantage of severe underrelaxation is reexamined and clarified. The relationship to solutions obtained by applying SOR methods to the equationRR ^T y=f is investigated.The work of this autor was supported by a research grant from the Natural Sciences and Engineering Research Council of Canada     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).