Implementation of a restarted Krylov subspace method for the evaluation of matrix functions

A new implementation of restarted Krylov subspace methods for evaluating f(A)b for a function f, a matrix A and a vector b is proposed. In contrast to an implementation proposed previously, it requires constant work and constant storage space per restart cycle. The convergence behavior of this scheme is discussed and a new stopping criterion based on an error indicator is given. The performance of the implementation is illustrated for three parabolic initial value problems, requiring the evaluation of exp(A)b.     

Polynomial approximation on the sphere using scattered data

We consider the problem of approximately reconstructing a function f defined on the surface of the unit sphere in the Euclidean space ℝ^{q +1} by using samples of f at scattered sites. A central role is played by the construction of a new operator for polynomial approximation, which is a uniformly bounded quasi‐projection in the de la Vallée Poussin style, i.e. it reproduces spherical polynomials up to a certain degree and has uniformly bounded L^p operator norm for 1 ≤ p ≤ ∞. Using certain positive quadrature rules for scattered sites due to Mhaskar, Narcowich and Ward, we discretize this operator obtaining a polynomial approximation of the target function which can be computed from scattered data and provides the same approximation degree of the best polynomial approximation. To establish the error estimates we use Marcinkiewicz–Zygmund inequalities, which we derive from our continuous approximating operator. We give concrete bounds for all constants in the Marcinkiewicz–Zygmund inequalities as well as in the error estimates. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Polarity of chordal graphs

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm.     

On mean approximation by polynomials with gaps on Caratheodory sets

The paper presents some new results on the possibility of approximation by polynomials with gaps. The approximations are done in the norm of the space L _p , 1 ≤ p < + ∞, on the Caratheodory sets in the complex plane. The lacunary versions of some results by Farell—Markushevich, S. Sinanian, A. L. Shahinian are obtained (Theorems 1, 3, 5). Similar approximations by the real parts of lacunary polynomials are given (Theorems 2, 4, 6). Dedicated to the memory of academician S. N. Mergelyan     

An application of Newton–Puiseux charts to the Jacobian problem

We study 2-dimensional Jacobian maps using so-called Newton–Puiseux charts. These are multi-valued coordinates near divisors of resolutions of indeterminacies at infinity of the Jacobian map in the source space as well as in the target space. The map expressed in these charts takes a very simple form, which allows us to detect a series of new analytical and topological properties. We prove that the Jacobian Conjecture holds true for maps (f,g) whose topological degree is ≤5, for maps with gcd(degf,degg)≤16 and for maps with. gcd(degf,degg) equal to 2 times a prime.     

Uniformly attracting solutions of nonautonomous differential equations

Understanding the structure of attractors is fundamental in nonautonomous stability and bifurcation theory. By means of clarifying theorems and carefully designed examples we highlight the potential complexity of attractors for nonautonomous differential equations that are as close to autonomous equations as possible. We introduce and study bounded uniform attractors and repellors for nonautonomous scalar differential equations, in particular for asymptotically autonomous, polynomial, and periodic equations. Our results suggest that uniformly attracting or repelling solutions are the true analogues of attracting or repelling fixed points of autonomous systems. We provide sharp conditions for the autonomous structure to break up and give way to a bewildering diversity of nonautonomous bifurcations.     

Noise suppresses exponential growth under regime switching

Consider a given system under regime switching whose solution grows exponentially, and suppose that the system is subject to environmental noise in some regimes. Can the regime switching and the environmental noise work together to make the system change significantly? The answer is yes. In this paper, we will show that the regime switching and the environmental noise will make the original system whose solution grows exponentially become a new system whose solutions will grow at most polynomially. In other words, we reveal that the regime switching and the environmental noise will suppress the exponential growth.     

Sums of characteristic values of compact polynomial operator pencils

We consider polynomial pencils whose coefficients are compact operators. Bounds for the sums of absolute values, real and imaginary parts of characteristic values are derived. Applications to differential and difference equations are discussed.     

Polynomial chaos representation of spatio-temporal random fields from experimental measurements

Two numerical techniques are proposed to construct a polynomial chaos (PC) representation of an arbitrary second-order random vector. In the first approach, a PC representation is constructed by matching a target joint probability density function (pdf) based on sequential conditioning (a sequence of conditional probability relations) in conjunction with the Rosenblatt transformation. In the second approach, the PC representation is obtained by having recourse to the Rosenblatt transformation and simultaneously matching a set of target marginal pdfs and target Spearman’s rank correlation coefficient (SRCC) matrix. Both techniques are applied to model an experimental spatio-temporal data set, exhibiting strong non-stationary and non-Gaussian features. The data consists of a set of oceanographic temperature records obtained from a shallow-water acoustics transmission experiment [1]. The measurement data, observed over a finite denumerable subset of the indexing set of the random process, is treated as a collection of observed samples of a second-order random vector that can be treated as a finite-dimensional approximation of the original random field. A set of properly ordered conditional pdfs, that uniquely characterizes the target joint pdf, in the first approach and a set of target marginal pdfs and a target SRCC matrix, in the second approach, are estimated from available experimental data. Digital realizations sampled from the constructed PC representations based on both schemes capture the observed statistical characteristics of the experimental data with sufficient accuracy. The relative advantages and disadvantages of the two proposed techniques are also highlighted.     

关于有向网络容量扩充问题

提出了有向网络最大容量的两种计算方法,将杨超等人（1998）的无向网络容量扩充问题,扩展到约束条件含固定费用的有向网络的扩充,并给出了强多项式算法。