Multidimensional butterfly factorization

This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size $N\times N$ with a product of $O(\log ?N)$ sparse matrices, each of which contains $O(N)$ nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in $O(1)$ operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms.     

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via δ$\delta$-covers, J. Complexity, 21 (2005) 691–709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.     

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.     

Error Estimation in Preconditioned Conjugate Gradients

In practical problems, iterative methods can hardly be used without some acceleration of convergence, commonly called preconditioning, which is typically achieved by incorporation of some (incomplete or modified) direct algorithm as a part of the iteration. Effectiveness of preconditioned iterative methods increases with possibility of stopping the iteration when the desired accuracy is reached. This requires, however, incorporating a proper measure of achieved accuracy as a part of computation. The goal of this paper is to describe a simple and numerically reliable estimation of the size of the error in the preconditioned conjugate gradient method. In this way this paper extends results from [Z. Strakoš and P. Tichy, ETNA, 13 (2002), pp. 56–80] and communicates them to practical users of the preconditioned conjugate gradient method. AMS subject classification (2000) 15A06, 65F10, 65F25, 65G50     

A Unified Rounding Error Bound for Polynomial Evaluation

We present a unified rounding error bound for polynomial evaluation. The bound presented here takes the same general form for the evaluation of a polynomial written in any polynomial basis when the evaluation algorithm can be expressed as a linear recurrence or a first-order linear matrix recurrence relation. Examples of these situations are: Horner's algorithm in the evaluation of power series, Clenshaw's and Forsythe's algorithms in the evaluation of orthogonal polynomial series, de-Casteljau's algorithm for Bernstein polynomial series, the modification of Clenshaw's algorithms in the evaluation of Szeg polynomial series, and so on.     

Lifting,superadditivity, mixed integer rounding and single node flow sets revisited

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0-1 single node flow set.Received: December 2002, Revised: April 2003, AMS classification: 90C11, 90C27Laurence A. Wolsey: Corresponding author: CORE, Voie du Roman Pays 34, 1348 Louvain-la-Neuve, Belgium. The first author is supported by the FNRS as a research fellow. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Ministers Office, Science Policy Programming. The scientific responsibility is assumed by the authors.Laurence A. Wolsey: This research was also supported by the European Commission GROWTH Programme, Research Project LISCOS, Large Scale Integrated Supply Chain Optimization Software Based on Branch-and-Cut and Constraint Programming Methods, Contract No. GRDI-1999-10056, and the project TMR-DONET nr. ERB FMRX-CT98-0202.     

Randomized strategies for the plurality problem

We consider a game played by two players, Paul and Carol. At the beginning of the game, Carol fixes a coloring of n balls. At each turn, Paul chooses a pair of the balls and asks Carol whether the balls have the same color. Carol truthfully answers his question. Paul’s goal is to determine the most frequent (plurality) color in the coloring by asking as few questions as possible. The game is studied in the probabilistic setting when Paul is allowed to choose his next question randomly.We give asymptotically tight bounds both for the case of two colors and many colors. For the balls colored by k colors, we prove a lower bound Ω(kn) on the expected number of questions; this is asymptotically optimal. For the balls colored by two colors, we provide a strategy for Paul to determine the plurality color with the expected number of questions; this almost matches the lower bound .     

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP∩CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity , which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).     

Nonsingularity,positive definiteness,and positive invertibility under fixed-point data rounding

For a real square matrix A and an integer d ? 0, let A _(d) denote the matrix formed from A by rounding off all its coefficients to d decimal places. The main problem handled in this paper is the following: assuming that A _(d) has some property, under what additional condition(s) can we be sure that the original matrix A possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number α(d), computed solely from A _(d) (not from A), such that the following alternative holdsif d > α(d), then nonsingularity (positive definiteness, positive invertibility) of A _(d) implies the same property for A if d < α(d) and A _(d) is nonsingular (positive definite, positive invertible), then there exists a matrix A′ with A′_(d) = A _(d) which does not have the respective property.For nonsingularity and positive definiteness the formula for α(d) is the same and involves computation of the NP-hard norm ‖ · ‖_∞,1; for positive invertibility α(d) is given by an easily computable formula.