Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments —aimed at the improved efficiency of the algorithm — are presented. This research was supported in part by National Science Foundation Grant No. DCR-8401098-A0l.     

Coreduction Homology Algorithm

This paper presents a new reduction algorithm for the efficient computation of the homology of cubical sets and polotypes. The algorithm—particularly strong for low-dimensional sets embedded in high dimensions—runs in linear time. The paper presents the theoretical background of the algorithm, the algorithm itself, experimental results based on an implementation for cubical sets as well as some theoretical complexity estimates. Both authors are partially supported by Polish MNSzW, Grant N201 037 31/3151.     

Collars and partitions of hyperbolic cone-surfaces

For compact Riemann surfaces, the collar theorem and Bers’ partition theorem are major tools for working with simple closed geodesics. The main goal of this article is to prove similar theorems for hyperbolic cone-surfaces. Hyperbolic two-dimensional orbifolds are a particular case of such surfaces. We consider all cone angles to be strictly less than π to be able to consider partitions. Emily B. Dryden—partially supported by the US National Science Foundation grant DMS-0306752. Hugo Parlier—supported by the Swiss National Science Foundation grants 21-57251.99 and 20-68181.02.     

On riesz subsets of abelian discrete groups

We study the class of the Riesz subsets of abelian discrete groups, that is, the sets for which the F. and M. Riesz theorem extends. We show that the “classical” tools of the theory — Riesz projections, localization in the Bohr sense, products — are leading to Riesz sets which are satisfying nice additional properties, e.g., the Mooney-Havin result extends to this class. We give an alternative proof of a result of A. B. Alexandrov, and we improve a construction of H. P. Rosenthal. The connection is made between this class and theM-structure theory. We show a result of convergence at the boundary for holomorphic functions on the polydisc. The Bourgain-Davis result on convergence of analytic martingales is improved.     

Generators of some Ramanujan formulas

In this paper we prove some Ramanujan type formulas for 1/π but without using the theory of modular forms. Instead we use the WZ—method created by H. Wilf and D. Zeilberger and find some hypergeometric functions in two variables which are second components of WZ—pairs than can be certified using Zeilberger's EKHAD package. These certificates have an additional property which allows us to get generalized Ramanujan's type series which are routinely proven by computer. We call these second hypergeometric components of the WZ—pairs generators. Finding generators seems a hard task but using a kind of experimental research (explained below), we have succeeded in finding some of them. Unfortunately we have not found yet generators for the most impressive Ramanujan's formulas. We also prove some interesting binomial sums for the constant 1/π². Finally we rewrite many of the obtained series using pochhammer symbols and study the rate of convergence. 2000 Mathematics Subject Classification Primary—33C20     

Efficient solution methods for covering tree problems

In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems—the Maximal Direct and Indirect Covering Tree problems—were introduced by Hutson and ReVelle. Previous solution techniques are extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered is attenuated by distance. It is also shown that the corresponding problem is NP-hard when the underlying network is not a tree.     

On theoretical and practical acceleration of randomized computation of the determinant of an integer matrix

We reexamine the Wiedemann—Coppersmith—Kaltofen—Villard algorithm for randomized computation of the determinant of an integer matrix and substantially simplify and accelerate its bottleneck stage of computing the minimum generating matrix polynomial, to make the algorithm practically promising while keeping it asymptotically fast. Bibliography: 58 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 163–187.     

Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper

The aim of the paper is to relate computational and arithmetic questions about Euler’s constant γ with properties of the values of the q-logarithm function, with natural choice of~q. By these means, we generalize a classical formula for γ due to Ramanujan, together with Vacca’s and Gosper’s series for γ, as well as deduce irrationality criteria and tests and new asymptotic formulas for computing Euler’s constant. The main tools are Euler-type integrals and hypergeometric series. 2000 Mathematics Subject Classification Primary—11Y60; Secondary—11J72, 33C20, 33D15 The work of the second author is supported by an Alexander von Humboldt research fellowship Dedication: To Leonhard Euler on his 300th birthday.     

Mixed Volume Computation for Semi-Mixed Systems

Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

Optimal Control for Two-Dimensional Stochastic Navier-Stokes Equations

Loeb space methods are used to prove the existence of an optimal control for the two-dimensional stochastic Navier--Stokes equations in a variety of settings—including that of control based on digital observations of the evolution of the solution.     

Mixed Volume Computation for Semi-Mixed Systems

   Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

Stochastic vendor selection problem: chance-constrained model and genetic algorithms

We study a vendor selection problem in which the buyer allocates an order quantity for an item among a set of suppliers such that the required aggregate quality, service, and lead time requirements are achieved at minimum cost. Some or all of these characteristics can be stochastic and hence, we treat the aggregate quality and service as uncertain. We develop a class of special chance-constrained programming models and a genetic algorithm is designed for the vendor selection problem. The solution procedure is tested on randomly generated problems and our computational experience is reported. The results demonstrate that the suggested approach could provide managers a promising way for studying the stochastic vendor selection problem. The authors would like to thank the referees for providing constructive comments that led to an improved version of the paper. Also, this research was partially supported by grants from National Natural Science Foundation (60776825)—China, 863 Programs (2007AA11Z208)—China, Doctorate Foundation (20040004012)—China, Villanova University Research Sabbatical Fall 2006, and the National Science Foundation (0332490)—USA.     

Twisted convolution and Riesz means

We improve a result of Thangavelu on Riesz means associated with the twisted Laplacian. Askey—Wainger estimates for Laguerre functions are the main tools used. Research supported in part by KBN grants and by ECC under program “Fourier Analysis” contract no: CIPDCT 940001.     

Higher order numerical differentiation on the Infinity Computer

There exist many applications where it is necessary to approximate numerically derivatives of a function which is given by a computer procedure. In particular, all the fields of optimization have a special interest in such a kind of information. In this paper, a new way to do this is presented for a new kind of a computer—the Infinity Computer—able to work numerically with finite, infinite, and infinitesimal numbers. It is proved that the Infinity Computer is able to calculate values of derivatives of a higher order for a wide class of functions represented by computer procedures. It is shown that the ability to compute derivatives of arbitrary order automatically and accurate to working precision is an intrinsic property of the Infinity Computer related to its way of functioning. Numerical examples illustrating the new concepts and numerical tools are given.     

Coreduction Homology Algorithm for Regular CW-Complexes

In this paper we present a new algorithm for computing the homology of regular CW-complexes. This algorithm is based on the coreduction algorithm due to Mrozek and Batko and consists essentially of a geometric preprocessing algorithm for the standard chain complex generated by a CW-complex. By employing the concept of S-complexes the original chain complex can—in all known practical cases—be reduced to a significantly smaller S-complex with isomorphic homology, which can then be computed using standard methods. Furthermore, we demonstrate that in the context of non-uniform cubical grids this method significantly improves currently available algorithms based on uniform cubical grids.     

Benchmarking optimization software with performance profiles

We propose performance profiles — distribution functions for a performance metric — as a tool for benchmarking and comparing optimization software. We show that performance profiles combine the best features of other tools for performance evaluation. Received: February 2001 / Accepted: May 2001?Published online October 2, 2001     

The Number of Spanning Trees in Self-Similar Graphs

The number of spanning trees of a graph, also known as the complexity, is computed for graphs constructed by a replacement procedure yielding a self-similar structure. It is shown that under certain symmetry conditions exact formulas for the complexity can be given. These formulas indicate interesting connections to the theory of electrical networks. Examples include the well-known Sierpiński graphs and their higher-dimensional analogues. Several auxiliary results are provided on the way—for instance, a property of the number of rooted spanning forests is proven for graphs with a high degree of symmetry.     

A cyclic scheduling problem with an undetermined number of parallel identical processors

This paper presents two integer linear programming (ILP) models for cyclic scheduling of tasks with unit/general processing time. Our work is motivated by digital signal processing (DSP) applications on FPGAs (Field-Programmable Gate Arrays)—hardware architectures hosting several sets of identical arithmetic units. These hardware units can be formalized as dedicated sets of parallel identical processors. We propose a method to find an optimal periodic schedule of DSP algorithms on such architectures where the number of available arithmetic units must be determined by the scheduling algorithm with respect to the capacity of the FPGA circuit. The emphasis is put on the efficiency of the ILP models. We show the advantages of our models in comparison with common ILP models on benchmarks and randomly generated instances.