Modifiable low‐rank approximation to a matrix

A truncated ULV decomposition (TULVD) of an m×n matrix X of rank k is a decomposition of the form X = ULV^T+E, where U and V are left orthogonal matrices, L is a k×k non‐singular lower triangular matrix, and E is an error matrix. Only U,V, L, and ∥E∥_F are stored, but E is not stored. We propose algorithms for updating and downdating the TULVD. To construct these modification algorithms, we also use a refinement algorithm based upon that in (SIAM J. Matrix Anal. Appl. 2005; 27 (1):198–211) that reduces ∥E∥_F, detects rank degeneracy, corrects it, and sharpens the approximation. Copyright © 2009 John Wiley & Sons, Ltd.     

A Note on an Error Bound for the AOR Method

Suppose Ax = b is a system of linear equations where the matrix A is symmetric positive definite and consistently ordered. A bound for the norm of the errors _k = x– x ^k of the AOR method in terms of the norms of _k = x ^k–x ^k–1 and _k+1 = x ^k+1–x ^k and their inner product is derived.     

A variational approach in weighted Sobolev spaces to the operator −Δ+∂/∂x 1 in exterior domains of ℝ3

Consider the Dirichlet problem −vΔu+k∂ ₁ u = f withv, k>0 in ℝ³ or in an exterior domain of ℝ³ where the skew-symmetric differential operator −₁=∂/∂x₁ is a singular perturbation of the Laplacian. Because of the inhomogeneity of the fundamental solution we study existence, uniqueness and regularity in Sobolev spaces with anisotropic weights. In these spaces the operator ∂₁ yields an additional positive definite term giving better results than in Sobolev spaces with radial weights. The elliptic equation −vΔu +k∂₁ u=f can be taken as a model problem for the Oseen equations, a linearized form of the Navier-Stokes equations. Supported by the Sonderforschungsbereich 256 of the Deutsche Forschungsgemeinschaft at the University of Bonn     

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN‐CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT ‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for any k. The MIN‐Ek‐LIN2 problems are equivalent to the k‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003     

<Emphasis Type="Italic">k</Emphasis>-Idempotency of linear combinations of an idempotent matrix and a tripotent matrix that commute

A complete solution is established to the problem of characterizing all situations in which a linear combination C = c ₁ A+c ₂ B of an idempotent matrix A and a tripotent matrix B is k-idempotent. As a special case of this, a set of necessary and sufficient conditions for a linear combination C = c ₁ A+c ₂ B to be k-idempotent when A and B are idempotent matrices, is also studied in this paper.     

A modified truncated singular value decomposition method for discrete ill‐posed problems

Truncated singular value decomposition is a popular method for solving linear discrete ill‐posed problems with a small to moderately sized matrix A. Regularization is achieved by replacing the matrix A by its best rank‐k approximant, which we denote by A_k. The rank may be determined in a variety of ways, for example, by the discrepancy principle or the L‐curve criterion. This paper describes a novel regularization approach, in which A is replaced by the closest matrix in a unitarily invariant matrix norm with the same spectral condition number as A_k. Computed examples illustrate that this regularization approach often yields approximate solutions of higher quality than the replacement of A by A_k.Copyright © 2014 John Wiley & Sons, Ltd.     

On the null-controllability of linear discrete-time systems with restrained controls

This paper is devoted to the null-controllability problem for linear, autonomous, discrete-time systems with restrained controls, i.e., systems described by the equationx _k+1=Ax _k+u _k,u _k , where 0 , but is not necessarily an interior point of . Some criteria for local and global null controllability are given with proofs. These results can be considered as extensions to discrete-time systems of the known corresponding criteria for linear, continuous-time systems.     

On the convergence of general stationary iterative methods for range‐Hermitian singular linear systems

General stationary iterative methods with a singular matrix M for solving range‐Hermitian singular linear systems are presented, some convergence conditions and the representation of the solution are also given. It can be verified that the general Ortega–Plemmons theorem and Keller theorem for the singular matrix M still hold. Furthermore, the singular matrix M can act as a good preconditioner for solving range‐Hermitian linear systems. Numerical results have demonstrated the effectiveness of the general stationary iterations and the singular preconditioner M. Copyright © 2009 John Wiley & Sons, Ltd.     

The solvability conditions for inverse eigenproblem of symmetric and anti‐persymmetric matrices and its approximation

The problem of generating a matrix A with specified eigen‐pair, where A is a symmetric and anti‐persymmetric matrix, is presented. An existence theorem is given and proved. A general expression of such a matrix is provided. We denote the set of such matrices by ??????_Eⁿ. The optimal approximation problem associated with ??????_Eⁿ is discussed, that is: to find the nearest matrix to a given matrix A* by A∈??????_Eⁿ. The existence and uniqueness of the optimal approximation problem is proved and the expression is provided for this nearest matrix. Copyright © 2002 John Wiley & Sons, Ltd.     

Computing the nearest stable matrix pairs

In this paper, we study the nearest stable matrix pair problem: given a square matrix pair (E,A), minimize the Frobenius norm of (Δ_E,Δ_A) such that (E+Δ_E,A+Δ_A) is a stable matrix pair. We propose a reformulation of the problem with a simpler feasible set by introducing dissipative Hamiltonian matrix pairs: A matrix pair (E,A) is dissipative Hamiltonian if A=(J−R)Q with skew‐symmetric J, positive semidefinite R, and an invertible Q such that Q^TE is positive semidefinite. This reformulation has a convex feasible domain onto which it is easy to project. This allows us to employ a fast gradient method to obtain a nearby stable approximation of a given matrix pair.     

Approximate inverse computation using Frobenius inner product

Parallel preconditioners are presented for the solution of general linear systems of equations. The computation of these preconditioners is achieved by orthogonal projections related to the Frobenius inner product. So, min_M∈??∥AM?I∥ _F and matrix M₀∈?? corresponding to this minimum (?? being any vectorial subspace of ??_n(?)) are explicitly computed using accumulative formulae in order to reduce computational cost when subspace ?? is extended to another one containing it. Every step, the computation is carried out taking advantage of the previous one, what considerably reduces the amount of work. These general results are illustrated with the subspace of matrices M such that AM is symmetric. The main application is developed for the subspace of matrices with a given sparsity pattern which may be constructed iteratively by augmenting the set of non‐zero entries in each column. Finally, the effectiveness of the sparse preconditioners is illustrated with some numerical experiments. Copyright © 2002 John Wiley & Sons, Ltd.     

Special orthogonal splittings of<Emphasis Type="Italic">L</Emphasis><Stack><Subscript>1</Subscript><Superscript>2<Emphasis Type="Italic">k</Emphasis></Superscript></Stack>

We show that for each positive integerk there is ak×k matrixB with ±1 entries such that puttingE to be the span of the rows of thek×2k matrix [√kI _k,B], thenE,E ^⊥ is a Kashin splitting: TheL ₁ ^2k and theL ₂ ^2k are universally equivalent on bothE andE ^⊥. Moreover, the probability that a random ±1 matrix satisfies the above is exponentially close to 1. Supported by the Israel Science Foundation.     

An eulerian trail traversing specified edges in given order

The following results are proved in this paper. Let G be a 2k-edge-connected eulerian graph. (i) For every set {e₁, e₂, ?, e_2k+1} ? E(G) there is an eulerian trail T of the form e₁, e₂, ?, e_2k+1, ?. (ii) For every set E* = {e₁, e₂, ?, e_k} ? E(G) there is an eulerian trail T = e₁, ?, e₂, ?, e_k, ? in which the elements of E* are traversed in accordance with a prescribed orientation. © 1995 John Wiley & Sons, Inc.     

An Optimal Control Problem for a Singular System of Solid–Liquid Phase Transition

In this article, we deal with a control problem for a singular system regarding a phase-field model which describes a solid–liquid transition by the Ginzburg–Landau theory. The purpose is to control the system by the means of the heat supply r able to guide it into a certain state with a solid (or liquid) part in a prescribed subset Ω₀ of the space domain Ω, and maintain it in this state during a period of time. The transition is described by a nonlinear differential system of two equations for the phase field and temperature. The control problem is set for some expressions of the cost functional which might reveal cases of physical interest. An approximating control problem is introduced and the existence of at least an optimal pair is proved. The first-order optimality conditions for the approximating problem are determined and a convergence result is given.     

Enhanced Group Analysis and Exact Solutions of Variable Coefficient Semilinear Diffusion Equations with a Power Source

A new approach to group classification problems and more general investigations on transformational properties of classes of differential equations is proposed. It is based on mappings between classes of differential equations, generated by families of point transformations. A class of variable coefficient (1+1)-dimensional semilinear reaction–diffusion equations of the general form f(x)u _t =(g(x)u _x ) _x +h(x)u ^m (m≠0,1) is studied from the symmetry point of view in the framework of the approach proposed. The singular subclass of the equations with m=2 is singled out. The group classifications of the entire class, the singular subclass and their images are performed with respect to both the corresponding (generalized extended) equivalence groups and all point transformations. The set of admissible transformations of the imaged class is exhaustively described in the general case m≠2. The procedure of classification of nonclassical symmetries, which involves mappings between classes of differential equations, is discussed. Wide families of new exact solutions are also constructed for equations from the classes under consideration by the classical method of Lie reductions and by generation of new solutions from known ones for other equations with point transformations of different kinds (such as additional equivalence transformations and mappings between classes of equations).     

A Classification of Quasi-Newton Methods

In this paper, we consider quasi-Newton methods of the form x _k+1=x _k + _k f(x _k ), k=0,1,. . ., for the solution of the system of nonlinear equations f(x)=0. We present a classification of such methods based on different structures for the matrix _k and various criteria for its computation, issued from three different formulae. Many known methods can be put into this framework and new methods are also obtained.     

An algorithm for selecting a good value for the parameter c in radial basis function interpolation

The accuracy of many schemes for interpolating scattered data with radial basis functions depends on a shape parameter c of the radial basis function. In this paper we study the effect of c on the quality of fit of the multiquadric, inverse multiquadric and Gaussian interpolants. We show, numerically, that the value of the optimal c (the value of c that minimizes the interpolation error) depends on the number and distribution of data points, on the data vector, and on the precision of the computation. We present an algorithm for selecting a good value for c that implicitly takes all the above considerations into account. The algorithm selects c by minimizing a cost function that imitates the error between the radial interpolant and the (unknown) function from which the data vector was sampled. The cost function is defined by taking some norm of the error vector E = (E ₁, ... , E_N)^T where E _k = E_k = f_k - S^k x_k) and S _k is the interpolant to a reduced data set obtained by removing the point x _k and the corresponding data value f _k from the original data set. The cost function can be defined for any radial basis function and any dimension. We present the results of many numerical experiments involving interpolation of two dimensional data sets by the multiquadric, inverse multiquadric and Gaussian interpolants and we show that our algorithm consistently produces good values for the parameter c. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Mixed Symmetric Problem of Electroelasticity Theory for a Layer Weakened by Through-the-Thickness Tunnel Holes

A new solution procedure for spatial mixed symmetric problems of electroelasticity theory for a layer weakened by through-the-thickness holes is proposed. The boundary-value problem is reduced to a system of one-dimensional singular integral equations consisting of 4k (k = 1, 2, ...) equations. Calculation results for characteristic stresses are presented.     

The M/Ek/r machine interference model steady state equations and numerical solutions

This paper studies the machine interference problem in which the running times follow the negative exponential distribution, the repair times the Erlang distribution and the number of operatives is more than one. The steady state equations are derived and it is shown that unlike the case of the M/E_k/r ordinary queueing model, the solution cannot be taken in closed form. An efficient numerical procedure is developed instead, based on a decomposition principle. Tabulated results of the average number of machines running and the operative utilization for a range of the problem parameters are given, for the cases M/E₃/2 and M/E₃/3. A tentative conclusion for a closeness in performance between the models M/M/r and M/E_k/r is drawn.     

Concentration of Mechanical Stresses near a Hole in a Piezoceramic Layer

A new procedure for solving three-dimensional mixed antisymmetric problems of elasticity theory for a layer weakened by through tunnel holes is proposed. The boundary-value problem is reduced to a system of one-dimensional singular integral equations consisting of 3k (k = 1, 2, ...) equations. The calculation results for characteristic stresses are presented.