Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

High levelm-harmonic cardinal B-splines

We generalize the notion ofm-harmonic cardinal B-spline defined in [Rabut, [6c]] to obtain B-splines on an infinite regular grid, which are halfway between elementary B-splines and the Lagrangean cardinal spline function. We give the main properties of these functions: Fourier transform, decay when x , integration,P _k -reproduction (fork<-2m–1) of the associated B-spline approximation, etc. We show that, in some sense, high levelm-harmonic B-splines may be considered as a finer regular approximation of the Dirac distribution than the elementarym-harmonic B-splines are.     

Concerning the solution set ofAx=b whereP≦A≦Q andp≦b≦q

Summary LetPQ ben×n real matrices so that ifPAQ for some matrixA, thenA is nonsingular. Letp andq ben-dimensional real column vectors. This paper determines the set of all solutionsx to the equationAx=b for allA andb so thatPAQ andpbq.     

The symmetric procrustes problem

The following symmetric Procrustes problem arises in the determination of the strain matrix of an elastic structure: find the symmetric matrixX which minimises the Frobenius (or Euclidean) norm ofAX — B, whereA andB are given rectangular matrices. We use the singular value decomposition to analyse the problem and to derive a stable method for its solution. A perturbation result is derived and used to assess the stability of methods based on solving normal equations. Some comparisons with the standard, unconstrained least squares problem are given.     

Jordan axioms for C*-algebras

A complex Banach spaceA which is also an associative algebra provided with a conjugate linear vector space involution * satisfying (a ²)^*=(a ^*)², aa ^* a=a³ and ab+ba2ab for alla, b inA is shown to be a C^*-algebra. The assumptions onA can be expressed in terms of the Jordan algebra obtained by symmetrization of the product ofA and are satisfied by any C^*-algebra. Thus we obtain a purely Jordan characterization of C^*-algebras.     

On spectral variations under bounded real matrix perturbations

Summary In this paper we investigate the set of eigenvalues of a perturbed matrix {ie509-1} whereA is given and ^{n × n}, ||< is arbitrary. We determine a lower bound for thisspectral value set which is exact for normal matricesA with well separated eigenvalues. We also investigate the behaviour of the spectral value set under similarity transformations. The results are then applied tostability radii which measure the distance of a matrixA from the set of matrices having at least one eigenvalue in a given closed instability domain _b.     

Joint convergence of conditional expectations

Let P_n, nIN{0}, be probability measures on a-fieldA; f_n, nIN{0}, be a family of uniformly boundedA-measurable functions andA _n, nIN, be a sequence of sub--fields ofA, increasing or decreasing to the-fieldA _o. It is shown in this paper that the conditional expectations converge in P_o-measure to with k, n, m , if P_n|A, nIN, converges uniformly to P_n|A and f_n, nIN, converges in P_o-measure to f_o.     

Optimally scaled matrices,necessary and sufficient conditions

Summary We shall in this paper consider the problem of determination a row or column scaling of a matrixA, which minimizes the condition number ofA. This problem was studied by several authors. For the cases of the maximum norm and of the sum norm the scale problem was completely solved by Bauer [1] and Sluis [5]. The condition ofA subordinate to the pair of euclidean norms is the ratio /, where and are the maximal and minimal eigenvalue of (A ^H A)^1/2 respectively. The euclidean case was considered by Forsythe and Strauss [3]. Shapiro [6] proposed some approaches to a numerical solution in this case. The main result of this paper is the presentation of necessary and sufficient conditions for optimal scaling in terms of maximizing and minimizing vectors. A uniqueness proof for the solution is offered provided some normality assumption is satisfied.     

A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations

Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ^{N, N} , withA nonsingular, andb ^N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.     

Perturbation analysis of the orthogonal procrustes problem

Given two arbitrary real matricesA andB of the same size, the orthogonal Procrustes problem is to find an orthogonal matrixM such that the Frobenius norm MA – B is minimized. This paper treats the common case when the orthogonal matrixM is required to have a positive determinant. The stability of the problem is studied and supremum results for the perturbation bounds are derived.     

A compactness property of Dedekind σ-completef-rings

We prove that Dedekind -completef-rings are boundedly countably atomic compact in the language (+, –, ·,, , ). This means that whenever is a countable set of atomic formulae with parameters from some Dedekind -completef-ringA every finite subsystem of which admits a solution in some fixed productK of bounded closed intervals ofA, then admits a solution inK.Presented by M. Henriksen.     

Hartley preconditioners for Toeplitz systems generated by positive continuous functions

In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT _n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM _n is defined to be the minimizer of T _n –B _{n F} over allB _n H _n whereH _n is the Hartley algebra. We show that if the generating functionf ofT _n is a positive 2-periodic continuous even function, then the spectrum of the preconditioned systemM _n ^–1 T _n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.     

Representations of free lattice-ordered groups

We show for any uncountable cardinal that the free groupG of rank has a linear right ordering on which the natural action of the free lattice-ordered groupF of rank is faithful and pathologically 2-transitive. As a consequence, we obtain results on the root system of prime subgroups ofF . This generalizes previous results of McCleary which required the generalized continuum hypothesis and to be regular.     

Preconditioning nonconforming finite element methods for treating Dirichlet boundary conditions. I

Summary This work deals with theL ² condition numbers and the distribution of theL ² singular values of the preconditioned operators {B _h ^–1 A_h}_{0, whereA h andB h are finite element discretizations of second order elliptic operators,A andB respectively. For conforming finite elements, it was shown in the work of Goldstein, Manteuffel and Parter that if the leading part ofB is a scalar multiple (1/) of the leading part ofA, then the singular values ofB h ^–1 A h cluster and fill-in the interval [ min, max], where 0< min max are the minimum and maximum of the factor . As a generalization of these results, the current work includes nonconforming finite element methods which deal with Dirichlet boundary conditions. It will be shown that, in this more general setting, theL ² condition numbers of {B h ^–1 A h } are uniformly bounded. Moreover, the singular values also cluster and fill-in the same interval. In particular, if the leading part ofB is the same as the leading part ofA, then the singular values cluster about the point {1}. Two specific methods are given as applications of this theory. They are the penalty method of Babuka and the method of nearly zero boundary conditions of Nitsche.This research was supported by the National Science Foundation under grant number DMS-8913091.}     

Tidy Noether lattices

A Noether lattice satisfying the union condition on primes which is not a domain and in which every nonzero principal element is integrally closed is characterized in terms of its direct summands. It is shown that either: (1) if has no proper nonzero direct summands, then every nonzero principal element of is integrally closed if and only if is a local Noether lattice whose maximal element is principal and has square zero; or (2) if has a proper nonzero direct summand, then every nonzero principal element of is integrally closed if and only if for each minimal direct summandA of, the quotient lattice [0,A] is an integrally closed domain.Presented by R. P. Dilworth.     

Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations

Summary We introduce a class of n×n structured matrices which includes three well-known classes of generalized companion matrices: tridiagonal plus rank-one matrices (comrade matrices), diagonal plus rank-one matrices and arrowhead matrices. Relying on the structure properties of , we show that if A then A=RQ , where A=QR is the QR decomposition of A. This allows one to implement the QR iteration for computing the eigenvalues and the eigenvectors of any A with O(n) arithmetic operations per iteration and with O(n) memory storage. This iteration, applied to generalized companion matrices, provides new O(n²) flops algorithms for computing polynomial zeros and for solving the associated (rational) secular equations. Numerical experiments confirm the effectiveness and the robustness of our approach.The results of this paper were presented at the Workshop on Nonlinear Approximations in Numerical Analysis, June 22 – 25, 2003, Moscow, Russia, at the Workshop on Operator Theory and Applications (IWOTA), June 24 – 27, 2003, Cagliari, Italy, at the Workshop on Numerical Linear Algebra at Universidad Carlos III in Leganes, June 16 – 17, 2003, Leganes, Spain, at the SIAM Conference on Applied Linear Algebra, July 15 – 19, 2003, Williamsburg, VA and in the Technical Report [8]. This work was partially supported by MIUR, grant number 2002014121, and by GNCS-INDAM. This work was supported by NSF Grant CCR 9732206 and PSC CUNY Awards 66406-0033 and 65393-0034.     

A note on best conditioned preconditioners

We discuss the solution of Hermitian positive definite systemsAx=b by the preconditioned conjugate gradient method with a preconditionerM. In general, the smaller the condition number(M ^–1/2 AM ^–1/2 ) is, the faster the convergence rate will be. For a given unitary matrixQ, letM _Q = {Q* _N Q | _n is ann-by-n complex diagonal matrix} andM _Q ⁺ ={Q* _n Q | _n is ann-by-n positive definite diagonal matrix}. The preconditionerM _b that minimizes(M ^–1/2 AM ^–1/2 ) overM _Q ⁺ is called the best conditioned preconditioner for the matrixA overM _Q ⁺ . We prove that ifQAQ* has Young's Property A, thenM _b is nothing new but the minimizer of M –A _F overM _Q . Here · _F denotes the Frobenius norm. Some applications are also given here.     

Decompositions of factor maps involving bi-closing maps

We describe all possible decompositions of a finite-to-one factor map : _A S, from an irreducible shift of finite type onto a sofic shift, into two maps =, such that the range of is a shift of finite type, and is bi-closing. We also give necessary and sufficient conditions for to be almost topologically conjugate overS to a bi-closing map.