A Characterization of the Riesz Probability Distribution

Bobecka and Wesolowski (Studia Math. 152:147–160, [2002]) have shown that, in the Olkin and Rubin characterization of the Wishart distribution (see Casalis and Letac in Ann. Stat. 24:763–786, [1996]), when we use the division algorithm defined by the quadratic representation and replace the property of invariance by the existence of twice differentiable densities, we still have a characterization of the Wishart distribution. In the present work, we show that when we use the division algorithm defined by the Cholesky decomposition, we get a characterization of the Riesz distribution.     

The Spectrum of the Independent Metropolis–Hastings Algorithm

In this paper we perform a spectral analysis for the kernel operator associated with the transition kernel for the Metropolis–Hastings algorithm that uses a fixed, location independent proposal distribution. Our main result is to establish the spectrum of the kernel operator T in the continuous case, thereby generalizing the results obtained by Liu in (Statist. Comput. 6, 113–119 1996) for the finite case.     

On one method of finding the equilibrium state

An algorithm for solving a linear “production-exchange” model is described. The model reduces to a parametric model with strictly concave utility functions. Some properties of the parametric model are studied. Since the excessive demand map satisfies the discovered preference condition, it is possible to apply the second form of Chebyshev centers. For a sufficiently small parameter, the algorithm converges to the equilibrium state of the initial linear model. Bibliography:11 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 80, 1996, pp. 59–67.     

On an integral equation in the theory of phase transitions for a system of magnetic rods

We study a nonlinear integral equation for the orientational distribution function (ODF) describing anisotropic nematic ordering in a system of magnetic rods. For highly elongated rods, we give a classification of bifurcation points and find their asymptotic behavior in the limits of small and large magnetic moments of the rods. We develop an algorithm to construct a nearly-isotropic ODF in the vicinity of the bifurcation point. We show that for both small and large magnetic moments, the ODF obtained has a left direction of bifurcation. However, for intermediate values of the magnetic moments, solutions with a right direction of bifurcation exist along with those with the left direction.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 109, No. 3, pp. 427–440, December, 1996.     

Finiteness of conical algorithms with ω-subdivisions

In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the so called ω-subdivision strategy is considered. It is proved that, for any given accuracy ε>0, this algorithm stops in a finite time by returning an ε-optimal solution for the problem, while it is convergent for ε=0. Received January 24, 1996 / Revised version received December 9, 1998 Published online June 11, 1999     

Free products of groups have no outer normal automorphisms

An automorphism of an arbitrary group is called normal if all subgroups of this group are left invariant by it. Lubotski [1] and Lue [2] showed that every normal automorphism of a noncyclic free group is inner. Here we prove that every normal automorphism of a nontrivial free product of groups is inner as well. Supported by RFFR grant No. 13-011-1513. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 562–566, September–October, 1996.     

The prox-Tikhonov regularization method for the proximal point algorithm in Banach spaces

It is known, by Rockafellar (SIAM J Control Optim 14:877–898, 1976), that the proximal point algorithm (PPA) converges weakly to a zero of a maximal monotone operator in a Hilbert space, but it fails to converge strongly. Lehdili and Moudafi (Optimization 37:239–252, 1996) introduced the new prox-Tikhonov regularization method for PPA to generate a strongly convergent sequence and established a convergence property for it by using the technique of variational distance in the same space setting. In this paper, the prox-Tikhonov regularization method for the proximal point algorithm of finding a zero for an accretive operator in the framework of Banach space is proposed. Conditions which guarantee the strong convergence of this algorithm to a particular element of the solution set is provided. An inexact variant of this method with error sequence is also discussed.     

Computing the dimension of a semi-algebraic set

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of R ^k, where R is a real closed field. We prove that the dimension k′ of a semi-algebraic set described by s polynomials of degree d in k variables can be computed in time

On consistent solutions for strategic games

Nash equilibria for strategic games were characterized by Peleg and Tijs (1996) as those solutions satisfying the properties of consistency, converse consistency and one-person rationality.  There are other solutions, like the ɛ-Nash equilibria, which enjoy nice properties and appear to be interesting substitutes for Nash equilibria when their existence cannot be guaranteed. They can be characterized using an appropriate substitute of one-person rationality. More generally, we introduce the class of “personalized” Nash equilibria and we prove that it contains all of the solutions characterized by consistency and converse consistency. Received January 1996/Final version December 1996     

Determination of reflector surfaces from near-field scattering data II. Numerical solution

Let be a nonisotropic point source of light, and the power intensity of this source in direction . Suppose that the light rays emitted by the source through an aperture fall on a perfectly reflecting surface and reflect off it so that the reflected rays illuminate a closed domain on some plane with intensity . The inverse problem consists of constructing the reflector surface from given position of the source , the input aperture , function , “target” set , and output intensity . For example, the input intensity may have a “bell”-like shape and we may wish to redistribute the energy uniformly over a prespecified region. The analytical formulation of the described above problem leads to a non-linear partial differential equation of Monge-Ampère type. In our previous paper we proved existence of weak solutions to this inverse problem and in this paper we describe and illustrate with examples an algorithm for its numerical solution. The proposed numerical method can be easily modified for the case when is a closed domain on an arbitrary surface. Received November 26, 1996     

Improved cyclic reduction for solving queueing problems

The cyclic reduction technique (Buzbee et al., 1970), rephrased in functional form (Bini and Meini, 1996), provides a numerically stable, quadratically convergent method for solving the matrix equation X = ∑^{+ ∞} _i=0 X_i A_i, where the A_i's are nonnegative k × k matrices such that ∑^{+ ∞} _i=0 A_i is column stochastic. In this paper we propose a further improvement of the above method, based on a point-wise evaluation/interpolation at a suitable set of Fourier points, of the functional relations defining each step of cyclic reduction (Bini and Meini,1996). This new technique allows us to devise an algorithm based on FFT having a lower computational cost and a higher numerical stability. Numerical results and comparisons are provided. This revised version was published online in August 2006 with corrections to the Cover Date.     

The rings of quotients of free algebras

It is proved that a symmetric Utumi ring of quotients, U, of a free associative (noncommutative) algebra F(X) with unity coincides with the algebra itself, U=F(X). From this, we obtain a similar statement concerning a symmetric Martindale ring of quotients, Q(F(X))=F(X), which is well known. In addition, it is shown that a left Martindale ring of quotients, F(X)_F, of a free algebra is a prime algebra and, moreover, every homogeneous element in a free algebra has the right inverse in F(X)_F but does not have the left one (unless, of course, r belongs to an underlying field). Since a left Utumi ring of quotients and a left Martindale ring of quotients for a free algebra both appear prime, an interesting question arises as to whether or not they coincide. Supported by RFFR grant No. 95-01-01356 and by ISF grant RPS000-RPS300. Translated fromAlgebra i Logika, Vol. 35, No. 6, pp. 655–662, November–December, 1996.     

A hybrid method for quantum global optimization

This paper gives a quantum algorithm for global optimization. The heart of such approaches employ Grover’s database search (1996; Phys Rev Lett 79(23):4709–4712, 1997a; 79(2):325–328, 1997b). Chi and Kim (1998) show that when the phases of the generalized Grover database search operator are optimally chosen, it is capable of finding a solution by a single query. To apply this method to global optimization requires knowledge of the number of marked points m to calculate the optimal phases, but this value is seldom known. This paper focuses on overcoming this hurdle by showing that an estimate of the optimal phases can be found and used to replace the optimal phases while maintaining a high probability of finding a solution. Merging this finding with a recently discovered dynamic quantum global optimization algorithm (BBW2D) that reduces the problem to finding successively improving regions using Grover’s search, we present a hybrid method that improves the efficiency and reduces the variance of the search algorithm when empirically compared to other existing quantum search algorithms.     

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday     

Hammocks and the Nazarova-Roiter Algorithm

Hammocks have been considered by Brenner [1], who gave a numericalcriterion for a finite translation quiver to be the Auslander–Reitenquiver of some representation-finite algebra. Ringel and Vossieck[11] gave a combinatorial definition of left hammocks whichgeneralised the concept of hammocks in the sense of Brenner,as a translation quiver H and an additive function h on H (calledthe hammock function) satisfying some conditions. They showedthat a thin left hammock with finitely many projective verticesis just the preprojective component of the Auslander–Reitenquiver of the category of S-spaces, where S is a finite partiallyordered set (abbreviated as ‘poset’). An importantrole in the representation theory of posets is played by twodifferentiation algorithms. One of the algorithms was developedby Nazarova and Roiter [8], and it reduces a poset S with amaximal element a to a new poset S'=_aS. The second algorithmwas developed by Zavadskij [13], and it reduces a poset S witha suitable pair (a, b) of elements a, b to a new poset S'=_(a,b)S.The main purpose of this paper is to construct new left hammocksfrom a given one, and to show the relationship between thesenew left hammocks and the Nazarova–Roiter algorithm. Ina later paper [5], we discuss the relationship between hammocksand the Zavadskij algorithm.     

Tiling groups: New applications in the triangular lattice

We first give a new presentation of an algorithm, from W. Thurston, to tile polygons with ``calissons' (i.e., lozenges formed from two cells of the triangular lattice Λ ). Afterward, we use a similar method to get a linear algorithm to tile polygons with m -leaning bars (parallelograms of length m formed from 2m cells of Λ ) and equilateral triangles (whose sides have length m ) and we produce a quadratic algorithm to tile polygons with m -leaning bars. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p189.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received July 3, 1996, and in revised form May 14, 1997.     

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces

Let Σ be a collection of n algebraic surface patches in of constant maximum degree b, such that the boundary of each surface consists of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement is O(n^{2+ɛ}), for any ɛ > 0, where the constant of proportionality depends on ɛ and on the maximum degree of the surfaces and of their boundaries. As an application, we obtain a near-quadratic motion-planning algorithm for general systems with three degrees of freedom. Received May 30, 1996, and in revised form February 18, 1997.     

The Beta-Jacobi Matrix Model,the CS Decomposition,and Generalized Singular Value Problems

We provide a solution to the β-Jacobi matrix model problem posed by Dumitriu and the first author. The random matrix distribution introduced here, called a matrix model, is related to the model of Killip and Nenciu, but the development is quite different. We start by introducing a new matrix decomposition and an algorithm for computing this decomposition. Then we run the algorithm on a Haar-distributed random matrix to produce the β-Jacobi matrix model. The Jacobi ensemble on , parametrized by β > 0, a > -1,and b > -1, is the probability distribution whose density is proportional to . The matrix model introduced in this paper is a probability distribution on structured orthogonal matrices. If J is a random matrix drawnfrom this distribution, then a CS decomposition can be taken,

Generalized biorthogonal bases and tridiagonalisation of matrices

Summary. In connection with the breakdown problem of the Lanczos algorithm a theory of generalized biorthogonal bases is developed. The connection between the generalized biorthogonal bases of Krylov chains and look-ahead Lanczos recursions is worked out in detail. It is shown how generalized biorthogonal bases with “antidiagonal blocks” can be constructed with small computational effort. Finally a special look-ahead Lanczos algorithm is derived which requires minimal computational effort and storage. Received September 21, 1995 / Revised version received August 12, 1996     

Simultaneous rational approximation to binomial functions

We apply Padé approximation techniques to deduce lower bounds for simultaneous rational approximation to one or more algebraic numbers. In particular, we strengthen work of Osgood, Fel´dman and Rickert, proving, for example, that

for (where the latter is an effective constant). Some of the Diophantine consequences of such bounds will be discussed, specifically in the direction of solving simultaneous Pell's equations and norm form equations.