Perturbation analysis of generalized saddle point systems

We discuss the perturbation analysis of generalized saddle point systems in this paper. We give the nonlinear perturbation bounds, then derive the condition numbers, and analyze the sensitivity of the computed solutions.     

Convergence analysis of trial free boundary methods for the two-dimensional filtration problem

Summary In this paper, we present a scheme of convergence analysis of trial free boundary methods for the two-dimensional filtration (or dam) problem. For the purpose we present a new variational principle of the filtration problem. This variational principle is defined on the set of admissible domains (candidates of the solution) in the dam. Under mild assumptions on the configuration of the dam, we may assume that all admissible domains are mapped from the unit disk by conformal mappings. Thus, proving convergence of trial free boundaries is reduced to proving convergence of the conformal mappings on the unit disk, and it is done using a method in the theory of minimal surfaces. Numerical examples are given.     

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.     

A greedy algorithm for the optimal basis problem

The following problem is considered. Givenm+1 points {x _i }₀ ^m inR ⁿ which generate anm-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the formx _i −x _j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrixf′ of a nonlinear mappingf by using values off computed atm+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination ofm pairs {x _i ,x _j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm inO(m ²) time. The complexity of this reduction is equivalent to onem×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is belowO(n ^2.376) form=n. Applications of the algorithm to interpolation methods are discussed. Part of the work was done while the author was visiting DIMACS, an NSF Science and Technology Center funded under contract STC-91-19999; DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore, NJ, USA.     

Solutions with compact support to the Cauchy problem of an equation modeling the motion of viscous droplets

The Cauchy problem to an equation arising in modeling the motion of viscous droplets is studied in the present paper. The authors prove that if the initial data has compact support, then there exists a weak solution which has compact support for all the time.     

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.     

Perturbation results for nearly uncoupled Markov chains with applications to iterative methods

Summary The standard perturbation theory for linear equations states that nearly uncoupled Markov chains (NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that shows that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping, criteria, iterative aggregation/disaggregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to Grassman, Taksar and Heyman was recently shown by O'Cinneide to achieve such bounds.Supported by the National Science Foundation under grant CCR-9000526 and its renewal, grant CCR-9201692. This research was done in part, during the author's visit to the Institute for Mathematics and its Applications, 514 Vincent Hall, 206 Church St. S.E., University of Minnesota, Minneapolis, MN 55455, USA     

Perturbation bounds for polynomials

Using two different elementary approaches we derive a global and a local perturbation theorem on polynomial zeros that significantly improve the results of Ostrowski (Acta Math 72:99–257, 1940), Elsner et al. (Linear Algebra Appl 142:195–209, 1990). A comparison of different perturbation bounds shows that our results are better in many cases than the similar local result of Beauzamy (Can Math Bull 42(1):3–12, 1999). Using the matrix theoretical approach we also improve the backward stability result of Edelman and Murakami (Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM, Philapdelphia, 1994; Math Comput 64:210–763, 1995).     

A method for the numerical solution of the one-dimensional inverse Stefan problem

Summary In this paper we suggest the use of complete families of solutions of the heat equation for the numerical solution of the inverse Stefan problem. Our approach leads to linear optimization problems which can be established and solved easily. Convergence results are proved. In a final section the method is applied to some examples.     

On condition numbers and algorithms for determining a rigid body movement

Using a set of landmarks to represent a rigid body, a rotation of the body can be determined in least-squares sense as the solution of an orthogonal Procrustes problem. We discuss some geometrical properties of the condition number for the problem of determining the orthogonal matrix representing the rotation. It is shown that the condition number critically depends on the configuration of the landmarks. The problem is also reformulated as an unconstrained nonlinear least-squares problem and the condition number is related to the geometry of such problems. In the common 3-D case, the movement can be represented by using a screw axis. Also the condition numbers for the problem of determining the screw axis representation are shown to closely depend on the configuration of the landmarks. The condition numbers are finally used to show that the used algorithms are stable.     

Cauchy problem for p-evolution equations

We consider p-evolution equations with real characteristics. We give a condition, on the lower order terms, that is sufficient for well-posedness of the Cauchy problem in Sobolev spaces.     

A noncharacteristic cauchy problem for the heat equation

The noncharacteristic Cauchy problem for the heat equation:% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiaadwhadaWgaaWcbaGaamiEaiaadIhaaeqaaOGaaiikaiaadIha% caGGSaGaamiDaiaacMcacqGH9aqpcaWG1bWaaSbaaSqaaiaadshaae% qaaOGaaiikaiaadIhacaGGSaGaamiDaiaacMcacaGGSaqefeKCPfgB% aGqbbiaa-bcacaaIWaWefv3ySLgznfgDOjdaryqr1ngBPrginfgDOb% cv39gaiyqacqGFKjcHcaWG4bGae4hzIqOae4ha3hJaaeymaiaabYca% caqGTaGaeuOhIuQaeuipaWJaaeiDaiabfYda8iabf6HiLkaacYcaca% WG1bGaaiikaiaaicdacaGGSaGaamiDaiaacMcacqGH9aqpcqqHvpGA% caGGOaGaamiDaiaacMcacaGGSaGaamyDamaaBaaaleaacaWG4baabe% aakiaacIcacaaIWaGaaiilaiaadshacaGGPaGaeyypa0JaaGiYdiaa% cIcacaWG0bGaaiykaiaacYcacaWFGaGaeuOhIuQaeuipaWJaamiDai% abfYda8iabf6HiLcaa!82F8!\[u_{xx} (x,t) = u_t (x,t), 0 \le x \le {\rm{1, - }}\infty < {\rm{t}} < \infty ,u(0,t) = \varphi (t),u_x (0,t) = \psi (t), \infty < t < \infty \]is considered. This problem is well-known to be ill-posed. The well-posedness class of the problem is described and some approximation schemes are proposed. For the case of inexactly given data, a mollification method is suggested.     

Robust weighted orthogonal regression in the errors-in-variables model

This paper focuses on robust estimation in the structural errors-in-variables (EV) model. A new class of robust estimators, called weighted orthogonal regression estimators, is introduced. Robust estimators of the parameters of the EV model are simply derived from robust estimators of multivariate location and scatter such as the M-estimators, the S-estimators and the MCD estimator. The influence functions of the proposed estimators are calculated and shown to be bounded. Moreover, we derive the asymptotic distributions of the estimators and illustrate the results on simulated examples and on a real-data set.     

Iterative refinement for constrained and weighted linear least squares

We present an algorithm for mixed precision iterative refinement on the constrained and weighted linear least squares problem, the CWLSQ problem. The approximate solution is obtained by solving the CWLSQ problem with the weightedQR factorization [6]. With backward errors for the weightedQR decomposition together with perturbation bounds for the CWLSQ problem we analyze the convergence behaviour of the iterative refinement procedure.In the unweighted case the initial convergence rate of the error of the iteratively refined solution is determined essentially by the condition number. For the CWLSQ problem the initial convergence behaviour is more complicated. The analysis shows that the initial convergence is dependent both on the condition of the problem related to the solution,x, and the vector =Wr, whereW is the weight matrix andr is the residual.We test our algorithm on two examples where the solution is known and the condition number of the problem can be varied. The computational test confirms the theoretical results and verifies that mixed precision iterative refinement, using the system matrix and the weightedQR decomposition, is an effective way of improving an approximate solution to the CWLSQ problem.     

On the Cauchy problem for the fast diffusion equation

For , the author studies the existence of a kind of weak solution to the Cauchy problem

     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

Error analysis of an algorithm for solving an underdetermined linear system

Summary The accumulation of rounding errors in a method used to compute the solution of an underdetermined system of linear equations at the least distance from a given point is being studied. The method used is based on orthogonal matrix decompositions.This research was partially supported by the Progetto Finalizzato Informatica of the Italian National Research Council     

Direct and iterative solution of the generalized Dirichlet–Neumann map for elliptic PDEs on square domains

In this work we derive the structural properties of the Collocation coefficient matrix associated with the Dirichlet–Neumann map for Laplace’s equation on a square domain. The analysis is independent of the choice of basis functions and includes the case involving the same type of boundary conditions on all sides, as well as the case where different boundary conditions are used on each side of the square domain. Taking advantage of said properties, we present efficient implementations of direct factorization and iterative methods, including classical SOR-type and Krylov subspace (Bi-CGSTAB and GMRES) methods appropriately preconditioned, for both Sine and Chebyshev basis functions. Numerical experimentation, to verify our results, is also included.     

Perturbation analysis for block downdating of a Cholesky decomposition

Summary. Let the Cholesky decomposition of be , where is upper triangular. The Cholesky block downdating problem is to determine such that , where is a block of rows from the data matrix . We analyze the sensitivity of this block downdating problem of the Cholesky factorization. A measure of conditioning for the Cholesky block downdating is presented and compared to the single row downdating case. Received September 15, 1993     

Entire solutions in monostable reaction-advection-diffusion equations in infinite cylinders

This paper is concerned with entire solutions of a monostable reaction-advection-diffusion equation in infinite cylinders without the condition f^′(u)≤f^′(0). By constructing a quasi-invariant manifold, we prove that there exist two classes of entire solutions. Furthermore, we show that one class of such entire solutions is unique up to space and time translation.