Error bounds for computed eigenvalues and eigenvectors. II

Summary In this paper, motivated by Symm-Wilkinson's paper [5], we describe a method which finds the rigorous error bounds for a computed eigenvalue ⁽⁰⁾ and a computed eigenvectorx ⁽⁰⁾ of any matrix A. The assumption in a previous paper [6] that ⁽⁰⁾,x ⁽⁰⁾ andA are real is not necessary in this paper. In connection with this method, Symm-Wilkinson's procedure is discussed, too.     

Cauchy's equation on Δ+: Further results

Summary In a previous paper [Cauchy's equation on ⁺, Aequationes Math.41 (1991), 192–211], we began the study of Cauchy's equation on ⁺, the space of probability distribution functions of nonnegative random variables. In this paper we continue this study and extend our previous results to triangle functions of the form _{T, L} , whereT is a continuous Archimedean t-norm andL a binary operation onR ⁺, which is iseomorphic to a strict t-conorm. We again use a lattice theoretic approach, and introduce first a theorem on the powers and roots of certain elements of ⁺ under _T,L . Under certain additional restrictions we obtain a representation of sup-continuous solutions, similar to the one found in the first paper.     

Convergence of stationary sequences for variational inequalities with maximal monotone operators

LetT be a maximal monotone operator defined on ^N . In this paper we consider the associated variational inequality 0 T(x ^*) and stationary sequences {x _k ^* for this operator, i.e., satisfyingT(x _k ^* 0. The aim of this paper is to give sufficient conditions ensuring that these sequences converge to the solution setT ^–1(0) especially when they are unbounded. For this we generalize and improve the directionally local boundedness theorem of Rockafellar to maximal monotone operatorsT defined on ^N .     

Existence of self-dual non-topological solutions in the Chern–Simons Higgs model

In this paper we investigate the existence of non-topological solutions of the Chern–Simons Higgs model in R². A long standing problem for this equation is: Given N vortex points and β>8π(N+1), does there exist a non-topological solution in R² such that the total magnetic flux is equal to β/2? In this paper, we prove the existence of such a solution if . We apply the bubbling analysis and the Leray–Schauder degree theory to solve this problem.     

Normal surfaces of degree 7 in ℙ n

Let Y be a surface of degree 7 of the complex projective space ⁿ , linearly normal and not contained in any hyperplane of ⁿ . The purpose of this paper is to describe the normal singular surfaces of degree 7 embedded in ⁿ , as above. The main contribution of this paper is to describe all normal singular projective surfaces with sectional genus 4.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

A note on skewcirculant preconditioners for elliptic problems

In a recent paper Chan and Chan study the use of circulant preconditioners for the solution of elliptic problems. They prove that circulant preconditioners can be chosen so that the condition number of the preconditioned system can be reduced fromO(n ² ) toO(n). In addition, using the Fast Fourier Transform, the computation of the preconditioner is highly parallelizable. To obtain their result, Chan and Chan introduce a shift /p/n ² for some >0. The aim of this paper is to consider skewcirculant preconditioners, and to show that in this case the condition number ofO(n) can easily be shown without using the somewhat unsatisfactory shift /p/n ². Furthermore, our estimates are more precise.     

Bessel Potentials with Logarithmic Components and Sobolev-Type Embeddings

In a recent paper Edmunds, Gurka, and Opic [5] showed that Sobolev spaces of order k, based on the Zygmund spaces L ^n/k (log L) (R ⁿ ), are continuously embedded into L (R ⁿ ) if > 1/p, p n/k. In this paper we replace L ^n/k (log L) (R ⁿ ) by the Lebesgue space L ^n/k (R ⁿ ) and increase the smoothness of the functions involved by a "logarithmic" order > 1/p to obtain the continuous embedding into L (R ⁿ ). Both approaches turn out to be equivalent. We also derive results of Trudinger-type [16] on embeddings into Orlicz spaces in the limit case k = n/p as well as results of Brézis-Wainger-type [2] on almost Lipschitz continuity in the superlimiting case k = n/p + 1.     

A “from scratch” proof of a theorem of Rockafellar and Fulkerson

The theorem of this paper is of the same general class as Farkas' Lemma, Stiemke's Theorem, and the Kuhn—Fourier Theorem in the theory of linear inequalities. LetV be a vector subspace ofR ⁿ , and let intervalsI ¹,, I ⁿ of real numbers be prescribed. A necessary and sufficient condition is given for existence of a vector (x ¹ ,, x ⁿ ) inV such thatx ⁱ I ⁱ (i = 1, ,n); this condition involves the elementary vectors (nonzero vectors with minimal support) ofV . The proof of the theorem uses only elementary linear algebra.The author at present holds a Senior Scientist Award of the Alexander von Humboldt Stiftung.     

Subdivision algorithms with nonnegative masks generally converge

In this paper, a subdivision scheme consists of an operator froml () tol () determined by a doubly infinite sequence, called the mask. This operator convolutes, in a certain sense, sequences l () with the mask, thus producing a new sequence inl (). Moreover, this new sequence is placed on a finer grid. If we iterate this process with a positive mask infinitely many times, it is known that this process will produce a continuous function, which we callf . In this paper, we consider the extent to which non-negative masks yield similar results. An important application of subdivision schemes in computer graphics is the generation of curves and surfaces from an initial sequence.     

Convergence in distribution and Skorokhod Convergence for the general theory of processes

Summary This paper proves some Skorokhod Convergence Theorems for processes with filtration. Roughly, these are theorems which say that if a family of processes with filtration (X ⁿ , ⁿ ),n, converges in distribution in a suitable sense, then there exists a family of equivalent processes (Y ⁿ , ⁿ ),n, which converges almost surely. The notion of equivalence used is that of adapted distribution, which guarantees that each (X ⁿ , ⁿ ) has the same stochastic properties as (X ⁿ , ⁿ ), with respect to its filtration, such as the martingale property or the Markov property. The appropriate notion of convergence in distribution is convergence in adapted distribution, which is developed in the paper. Fortunately, any tight sequence of processes has a subsequence which converges in adapted distribution. For discrete time processes, (Y ⁿ , ⁿ ),n, and their limit (Y, ) may be taken as all having the same fixed filtration ⁿ =. In the continuous time case, theY ⁿ , ⁿ may require different filtrations ⁿ , which converge to. To handle this, convergence of filtrations is defined and its theory developed.During part of the time this work was in progress, it was supported by an NSERC operating grant, and the author was an NSERC University Research Fellow. The author wishes to thank the Steklov Mathematical Institute of the Soviet Academy of Sciences for its hospitality while the principle research in this paper was being begun, A.N. Shiryaev and P.C. Greenwood, who made the author's visit there possible, and Ján Miná for his hospitality while that research was being finished. We thank the referee who suggested the results in Sect. 12     

OnH 2 minimization of theH ∞ suboptimal solutions

In this paper we show that theH ² minimization of theH suboptimal solutions for a class of suboptimalH distance problems can be reduced to a finite dimensional nonlinear optimization problem. This extends a result of [7] where the same problem is considered in the Caratheodory-Schur interpolation case.     

Optimization over the efficient set: overview

Over the past several decades, the optimization over the efficient set has seen a substantial development. The aim of this paper is to provide a state-of-the-art survey of the development. Given p linear criteria c ¹x,,c^p x and a feasible region X of R ⁿ, the linear multicriteria problem is to find a point x of X such that no point x' of X satisfies (c¹ x',,c^p x')(c¹ x,,c^p x) and (c¹x',,c^p x')q (c¹ x ,,c^p x). Such a point is called an efficient point. The optimization over the efficient set is the maximization of a given function over the set of efficient points. The difficulty of this problem is mainly due to the nonconvexity of this set. The existing algorithms for solving this problem could be classified into several groups such as adjacent vertex search algorithm, nonadjacent vertex search algorithm, branch-and-bound based algorithm, Lagrangian relaxation based algorithm, dual approach and bisection algorithm. In this paper we review a typical algorithm from each group and compare them from the computational point of view.     

Multipliers of a Family of Almost Modular Functions

The goal of this paper is to complete an investigation begun by Cohn and Knopp in their 1994 paper, Application of Dedekind eta-multipliers to modular equations. The paper concerned _k (z), a family of modular forms on ⁰(N) (N a positive integer) with possibly non-trivial multiplier systems. Cohn and Knopp defined new functions _k (z) and a new group containing ⁰(N) and proved that for all S in the larger group and for all k, _k (Sz) = M _k(S) _k (z), where M _k(S)²⁴ = 1. This yielded interesting invariance properties of _k , dependent on the values of M _k(S). Fixing a constant integer e, independent of k, Cohn and Knopp proved that for all k and all S in the larger group, M _k(S) ^e = (±1) ^e . They determined the sign of M _k(S) ^e in many, but not all, cases. In this paper, we give a complete determination of the values of M _k(S) ^e in the remaining cases.     

Harmonic morphisms from complex projective spaces

In this paper we study harmonic morphisms :U P ^m N ² from open subsets of complex projective spaces to Riemann surfaces. We construct many new examples of such maps which are not holomorphic with respect to the standard Kähler structure on P ^m.The research leading to this paper was supported by the Icelandic Science Fund and the Danish National Science Fund.     

Smooth classification of 1-resonant vector fields on ℝ3

In this paper we study on ⁿ a class of smoothly (C ) finitely determined vector fields which admit infinite many resonant relations. We give a complete classification of all such vector fields with arbitrarily degenerated nonlinear parts.     

J. Simons' type integral formula for hypersurfaces in a unit sphere

In this paper, by investigating compact rotational hypersurfaces Mⁿ in a unit sphere Sⁿ⁺¹(1), we get some integral formulas and then apply the integral formulas to characterize torus .     

Parallel Computation of Invariant Measures

Let S:[0,1][0,1] be a nonsingular transformation and let P:L ¹(0,1)L ¹(0,1) be the corresponding Frobenius–Perron operator. In this paper we propose a parallel algorithm for computing a fixed density of P, using Ulam's method and a modified Monte Carlo approach. Numerical results are also presented.     

Time-Localization of Random Distributions on Wiener Space II: Convergence,Fractional Brownian Density Processes

For a random element X of a nuclear space of distributions on Wiener space C([0,1],R ^d ), the localization problem consists in projecting X at each time t[0,1] in order to define an S(R ^d )-valued process X={X(t),t[0,1]}, called the time-localization of X. The convergence problem consists in deriving weak convergence of time-localization processes (in C([0,1],S(R ^d )) in this paper) from weak convergence of the corresponding random distributions on C([0,1],R ^d ). Partial steps towards the solution of this problem were carried out in previous papers, the tightness having remained unsolved. In this paper we complete the solution of the convergence problem via an extension of the time-localization procedure. As an example, a fluctuation limit of a system of fractional Brownian motions yields a new class of S(R ^d )-valued Gaussian processes, the fractional Brownian density processes.     

On accuracy of approximation of the spectral radius by the Gelfand formula

The famous Gelfand formula ρ(A)=limsup_n→∞A^n1/n for the spectral radius of a matrix is of great importance in various mathematical constructions. Unfortunately, the range of applicability of this formula is substantially restricted by a lack of estimates for the rate of convergence of the quantities A^n1/n to ρ(A). In the paper this deficiency is made up to some extent. By using the Bochi inequalities we establish explicit computable estimates for the rate of convergence of the quantities A^n1/n to ρ(A). The obtained estimates are then extended for evaluation of the joint spectral radius of matrix sets.