An iterative solution method for solving f(A)x = b,using Krylov subspace information obtained for the symmetric positive definite matrix A

The conjugate gradients method generates successive approximations x_i for the solution of the linear system Ax = b, where A is symmetric positive definite and usually sparse. It will be shown how intermediate information obtained by the conjugate gradients (cg) algorithm (or by the closely related Lanczos algorithm) can be used to solve f(A)x = b iteratively in an efficient way, for suitable functions f. The special case f(A) = A² is discussed in particular. We also consider the problem of solving Ax = b for different right-hand sides b. A variant on a well-known algorithm for that problem is proposed, which does not seem to suffer from the usual loss of orthogonality in the standard cg and Lanczos algorithms.     

A new method for computing the matrix exponential operation based on vector valued rational approximations

In this paper a new method for computing the action of the matrix exponential on a vector e^Atb, where A is a complex matrix and t is a positive real number, is proposed. Our approach is based on vector valued rational approximation where the approximants are determined by the denominator polynomials whose coefficients are obtained by solving an inexpensive linear least-squares problem. No matrix multiplications or divisions but matrix-vector products are required in the whole process. A technique of scaling and recurrence enables our method to be more effective when the problem is for fixed A,b and many values of t. We also give a backward error analysis in exact arithmetic for the truncation errors to derive our new algorithm. Preliminary numerical results illustrate that the new algorithm performs well.     

On a particular quadratic network problem

Let c(x), d(x) and h(x) be linear functions defined over a convex polyhedron X = {x | Ax = r and 0 ⩽ x ⩽ u }, where A is the node-edge incidence matrix of a given network. Let f(x) = c(x)d(x) + h(x) be a (particular) quadratic function which we intend to minimize over X. In this paper we use the theory of multiobjective programming do develop algorithms for the semidefinite positive case (f(x) = ϱ[d(x)]² + h(x) and ϱ is a strictly postive real constant) and the semidefinite negative case (f(x) = ϱ[d(x)]² + h (x) and ϱ is a strictly negative real constant). A special indefinite case (h(x) is constant over X) is also studied.In the proposed algorithms, basic solutions are used in all the interactions with possible exception for the last one. Moreover only the concepts of the simplex method are used; consequently these algorithms can be used even when A is not the node-edge incidence matrix of a network. However they are particularly attractive for the network case. In fact, network basic solutions are efficiently manipulated when appropriated data structures are used in the computational implementation of an algorithm.     

Determination of a matrix function using the divided difference method of Newton and the interpolation technique of Hermite

Computing a function f(A) of an n-by-n matrix A is a frequently occurring problem in control theory and other applications. In this paper we introduce an effective approach for the determination of matrix function f(A). We propose a new technique which is based on the extension of Newton divided difference and the interpolation technique of Hermite and using the eigenvalues of the given matrix A. The new algorithm is tested on several problems to show the efficiency of the presented method. Finally, the application of this method in control theory is highlighted.     

Uniqueness properties in finite-continuous additive measurement

Let ? be a binary relation on A×X, and suppose that there are real valued functions f on A and g on X such that, for all ax, by ∈ A×X, ax ? by if and only if f (a)+g(x) ? f(b)+g(y). This paper establishes uniqueness properties for f and g when A is a finite set, X is a real interval with g increasing on X, and for any a, b and x there is a y for which f(a)+g(x)=f(b)+g(y). The resultant uniqueness properties occupy an intermediate position among uniqueness properties for other structural cases of two-factor additive measurement.It is shown that f is unique up to a positive affine transformation (αf+β₁ with α > 0), but that g is unique up to a similar positive affine transformation (αg+β₂) if and only if the ratio [f(a)?f(b)]/[f(a)?f(c)] is irrational for some a, b, c ∈ A. When the f ratios are rational for all cases where they are defined, there will be a half-open interval (x₀, x₁) in X such that the restriction of g on (x₀, x₁) can be any increasing function for which sup {g(x)?g(x₀): x₀ ? x < x₁} does not exceed a specified bound, and, when g is thus defines on (x₀, x₁), it will be uniquely determined on the rest of X. In general, g must be continuous only in the ‘irrational’ case.     

On a new notion of the solution to an ill-posed problem

A new understanding of the notion of the stable solution to ill-posed problems is proposed. The new notion is more realistic than the old one and better fits the practical computational needs. A method for constructing stable solutions in the new sense is proposed and justified. The basic point is: in the traditional definition of the stable solution to an ill-posed problem Au=f, where A is a linear or nonlinear operator in a Hilbert space H, it is assumed that the noisy data {f_δ,δ} are given, ‖f−f_δ‖≤δ, and a stable solution u_δ:=R_δf_δ is defined by the relation lim_δ→0‖R_δf_δ−y‖=0, where y solves the equation Au=f, i.e., Ay=f. In this definition y and f are unknown. Any f∈B(f_δ,δ) can be the exact data, where B(f_δ,δ):={f:‖f−f_δ‖≤δ}.The new notion of the stable solution excludes the unknown y and f from the definition of the solution. The solution is defined only in terms of the noisy data, noise level, and an a priori information about a compactum to which the solution belongs.     

Relational systems with trivial endomorphisms and polymorphisms

A finitary relation ? and a finitary function f on some set A are said to be compatible one with the other if ? is a subalgebra of a suitable direct power of (A, f). In this paper properties for relational systems (A, Q) are derived in order to guarantee that every (finitary) function compatible with all relations of Q must be a projection or constant. The connection to interpolation properties is demonstrated and some open problems are stated.     

The least common multiple of a sequence of products of linear polynomials

Let f(x) be the product of several linear polynomials with integer coefficients. In this paper, we obtain the estimate log?lcm?(f(1),…,f(n))～An as n→∞, where A is a constant depending on?f.     

Eigenvalue inequalities for convex and log-convex functions

We give a matrix version of the scalar inequality f(a + b) ? f(a) + f(b) for positive concave functions f on [0, ∞). We show that Choi’s inequality for positive unital maps and operator convex functions remains valid for monotone convex functions at the cost of unitary congruences. Some inequalities for log-convex functions are presented and a new arithmetic-geometric mean inequality for positive matrices is given. We also point out a simple proof of the Bhatia-Kittaneh arithmetic-geometric mean inequality.     

Group Connectivity of 3-Edge-Connected Chordal Graphs

Let A be a finite abelian group and G be a digraph. The boundary of a function f: E(G)ZA is a function ‘f: V(G)ZA given by ‘f(v)=~_{e leaving v}f(e)m~_{e entering v}f(e). The graph G is A-connected if for every b: V(G)ZA with ~_{v] V(G)} b(v)=0, there is a function f: E(G)ZA{0} such that ‘f=b. In [J. Combinatorial Theory, Ser. B 56 (1992) 165-182], Jaeger et al showed that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̈́. It is conjectured that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̓ and that every 5-edge-connected graph is A-connected, for every abelian group A with |A|́.¶ In this note, we investigate the group connectivity of 3-edge-connected chordal graphs and characterize 3-edge-connected chordal graphs that are A-connected for every finite abelian group A with |A|́.     

Certain sufficient conditions of uniformity for systems of functions of many-valued logic

For any finite system A of functions of the k-valued logic taking values in the set E _s = {0,1,…, s ? 1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set E _s contains a near-unanimity function, it is proved that there exist constants c and d such that for an arbitrary function f ∈ [A] the depth D _A (f) and the complexity L _A (f) of f in the class of formulas over A satisfy the relation D _A (f) ≤ clog₂ L _A (f) + d.     

Topologically inseparable functions I: Finitary case

Given a finite set A and a distinguished function f: A → A, we study the set of all functions g: A → A that are continuous for all topologies for which f is continuous. The main result is a characterization of the functions f such that this set is trivial, that is, contains only the constant functions and the iterates of f.     

Practical computation of matrix functions

Several new representations for an analytic function f(A) of a complex matrix A, and in particular for e^At and A^t, are derived, which also are numerically useful in that they avoid the computation of eigenvalues of A.     

On the generalized Hyers-Ulam stability of module left derivations

Let A be a unital normed algebra and let M be a unitary Banach left A-module. If f:A→M is an approximate module left derivation, then f:A→M is a module left derivation. Moreover, if M=A is a semiprime unital Banach algebra and f(tx) is continuous in t∈R for each fixed x in A, then every approximately linear left derivation f:A→A is a linear derivation which maps A into the intersection of its center Z(A) and its Jacobson radical rad(A). In particular, if A is semisimple, then f is identically zero.     

The limiting behavior on the restriction of divisor classes to hypersurfaces

Let A be an excellent local normal domain and {f_n}_n=1^∞ a sequence of elements lying in successively higher powers of the maximal ideal, such that each hypersurface A/f_nA satisfies R₁. We investigate the injectivity of the maps Cl(A)→Cl((A/f_nA)′), where (A/f_nA)′ represents the integral closure. The first result shows that no non-trivial divisor class can lie in every kernel. Secondly, when A is, in addition, an isolated singularity containing a field of characteristic zero, dim A?4, and A has a small Cohen-Macaulay module, then we show that there is an integer N>0 such that if , then Cl(A)→Cl((A/f_nA)′) is injective. We substantiate these results with a general construction that provides a large collection of examples.     

Functions of operators under perturbations of class Sp

This is a continuation of our paper [2]. We prove that for functions f in the Hölder class Λα(R) and 1<p<∞, the operator f(A)−f(B) belongs to Sp/α, whenever A and B are self-adjoint operators with A−B∈Sp. We also obtain sharp estimates for the Schatten-von Neumann norms ‖f(A)−f(B)Sp/α_‖ in terms of ‖A−BSp_‖ and establish similar results for other operator ideals. We also estimate Schatten-von Neumann norms of higher order differences . We prove that analogous results hold for functions on the unit circle and unitary operators and for analytic functions in the unit disk and contractions. Then we find necessary conditions on f for f(A)−f(B) to belong to Sq under the assumption that A−B∈Sp. We also obtain Schatten-von Neumann estimates for quasicommutators f(A)R−Rf(B), and introduce a spectral shift function and find a trace formula for operators of the form f(A−K)−2f(A)+f(A+K).     

Compatibility of approximate solutions of inaccurate linear equations

For the equation Ax = b, a method is described which, given x₁ in addition to A and b, yields an operator A₁ and a vector b₁ such that A₁x₁ = b₁ and the distance of the pair (A₁,b₁) from (A,b) (for a class of metrics) is minimized. The special case of matrix equations and Hölder metrics is discussed explicitly.     

Strong commutativity preserving maps in prime rings with involution

Let A be a prime ring of characteristic not 2, with center Z(A) and with involution *. Let S be the set of symmetric elements of A. Suppose that f:S→A is an additive map such that [f(x),f(y)]=[x,y] for all x,y∈S. Then unless A is an order in a 4-dimensional central simple algebra, there exists an additive map μ:S→Z(A) such that f(x)=x+μ(x) for all x∈S or f(x)=-x+μ(x) for all x∈S.     

Continuous dependence on data for bilocal difference equations

The continuous dependence on data is studied for a class of second order difference equations governed by a maximal monotone operator A in a Hilbert space. A nonhomogeneous term f appears in the equation and some bilocal boundary conditions a, b are added. One shows that the function which associates to {a, b, A, f} the solution of this boundary value problem is continuous in a specific sense. One uses the convergence of a sequence of operators in the sense of the resolvent. The problem studied here is the discrete variant of a problem from the continuous case.     

Global minimization of multivariate polynomials using nonstandard methods

The purpose of this paper is to present two algorithms for global minimization of multivariate polynomials. For a multivariate real polynomial f, we provide an effective algorithm for deciding whether or not the infimum of f is finite. In the case of f having a finite infimum, the infimum of f can be accurately coded as (h; a, b), where h is a real polynomial in one variable, a and b is two rational numbers with a?<?b, and (h, a, b) stands for the only real root of h in the open interval ]a, b[. Moreover, another algorithm is provided to decide whether or not the infimum of f is attained when the infimum of f is finite. Our methods are called ??nonstandard??, because an infinitesimal element is introduced in our arguments.