A randomized sublinear time parallel GCD algorithm for the EREW PRAM

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+?) processors for any ?>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.     

Fast computation of the Smith form of a sparse integer matrix

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix . The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about black box evaluations for word-sized primes p and , plus additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about bit operations, where O(MM(m)) operations are sufficient to multiply two matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error. Received: March 9, 2000.     

A new factorization of the mass matrix for optimal serial and parallel calculation of multibody dynamics

This paper describes a new factorization of the inverse of the joint-space inertia matrix M. In this factorization, M ^?1 is directly obtained as the product of a set of sparse matrices wherein, for a serial chain, only the inversion of a block-tridiagonal matrix is needed. In other words, this factorization reduces the inversion of a dense matrix to that of a block-tridiagonal one. As a result, this factorization leads to both an optimal serial and an optimal parallel algorithm, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors. The novel feature of this algorithm is that it first calculates the interbody forces. Once these forces are known, the accelerations are easily calculated. We discuss the extension of the algorithm to the task of calculating the forward dynamics of a kinematic tree consisting of a single main chain plus any number of short side branches. We also show that this new factorization of M ^?1 leads to a new factorization of the operational-space inverse inertia, Λ ^?1, in the form of a product involving sparse matrices. We show that this factorization can be exploited for optimal serial and parallel computation of Λ ^?1, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors.     

Efficient region segmentation on compressed gray images using quadtree and shading representation

Image segmentation, which partitions the image into homogeneous regions, is a fundamental operation in image processing. Suppose the input gray image with size N×N has been compressed into the compressed image via quadtree and shading representation. Assume that the number of blocks in the representation is B, commonly B<N² due to the compression effect. This paper first derives some closed forms for computing the mean/variance of any block and for calculating the two statistical measures of any merged region in O(1) time. It then presents an efficient O(Bα(B))-time algorithm for performing region segmentation on the compressed image directly where α(B) is the inverse of the Ackerman's function and is a very slowly growing function. With the same time complexity, our results extend the pioneering results by Dillencourt and Samet from the map image to the gray image. In addition, with four real images, experimental results show that our proposed algorithm has about 55.4% execution time improvement ratio when compared to the previous fastest region-segmentation algorithm by Fiorio and Gustedt whose O(N²)-time algorithm is run on the original N×N gray image.     

An efficient approximation for the Generalized Assignment Problem

We present a simple family of algorithms for solving the Generalized Assignment Problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP. If the approximation ratio of the knapsack algorithm is α and its running time is O(f(N)), our algorithm guarantees a (1+α)-approximation ratio, and it runs in O(M⋅f(N)+M⋅N), where N is the number of items and M is the number of bins. Not only does our technique comprise a general interesting framework for the GAP problem; it also matches the best combinatorial approximation for this problem, with a much simpler algorithm and a better running time.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

Approximation algorithms for covering/packing integer programs

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums β_i=∑_jB_ij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(max_j∑_iA_ij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.     

Realization and synthesis of reversible functions

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N≤2ⁿ, and the other (2ⁿ−N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n⋅N ‘(n−1)’-CNOT gates and 4n²⋅N NOT gates. The time and space complexities of the algorithm are Ω(n⋅4ⁿ) and Ω(n⋅2ⁿ), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.     

The Mailman algorithm: A note on matrix-vector multiplication

Given an m×n matrix A we are interested in applying it to a real vector x∈Rn in less than the straightforward O(mn) time. For an exact deterministic computation at the very least all entries in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn/log(max{m,n})) operations. Algorithms for matrix-vector multiplication over finite fields, which save a log factor, have been known for many years. Our contribution is unique in its simplicity and in the fact that it applies also to real valued vectors. Using our algorithm improves on recent results for dimensionality reduction. It gives the first known random projection process exhibiting asymptotically optimal running time. The mailman algorithm is also shown to be useful (faster than naïve) even for small matrices.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

An improved algorithm on the content of realizable fuzzy matrices

An n×nn{\times}n fuzzy matrix A is called realizable if there exists an n×tn{\times}t fuzzy matrix B such that A=B\odot B^T,A=B\odot B^{T}, where \odot\odot is the max–min composition. Let r(A)=min{p:A=B\odot B^T, B ? L^n×p}.r(A)={min}\{p:A=B\odot B^{T}, B\in L^{n\times p}\}. Then r(A)r(A) is called the content of A. Since 1982, how to calculate r(A) for a given n×nn{\times}n realizable fuzzy matrix A was a focus problem, many researchers have made a lot of research work. X. P. Wang in 1999 gave an algorithm to find the fuzzy matrix B and calculate r(A) within [r(A)]ⁿ²[r(A)]^{n^{2}} steps. Therefore, to find a simpler algorithm is a problem what we have to consider. This paper makes use of the symmetry of the realizable fuzzy matrix A to simplify the algorithm of content r(A)r(A) based on the work of Wang (Chin Ann Math A 6: 701–706, 1999).     

Finding Maximum Edge Bicliques in Convex Bipartite Graphs

A bipartite graph G=(A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v??A, vertices adjacent to v are consecutive in?B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?³ nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n ²) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function.     

An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L)⋅m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L)⋅m² but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of cm, where c is a constant and m is the number of clauses?     

Faster parameterized algorithms for minor containment

The H-Minor containment problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. H-Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1-9], providing an algorithm that in time O(3^k2⋅(h+k−1)!⋅m) decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. In this work we improve the dependence on k of Hicks’ result by showing that checking if H is a minor of G can be done in time O(2^{(2k+1)⋅logk}⋅h^2k⋅2^2h2⋅m). We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time 2^O(k)⋅h^2k⋅2^O(h)⋅n, with n=∣V(G)∣. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment.     

An optimal storage format for sparse matrices

The irregular nature of sparse matrix-vector multiplication, Ax=y, has led to the development of a variety of compressed storage formats, which are widely used because they do not store any unnecessary elements. One of these methods, the Jagged Diagonal Storage format (JDS) is, in addition, considered appropriate for the implementation of iterative methods on parallel and vector processors. In this work we present the Transpose Jagged Diagonal Storage format (TJDS) which drew inspiration from the Jagged Diagonal Storage scheme but requires less storage space than JDS. We propose an alternative storage scheme which makes no assumptions about the sparsity pattern of the matrix and only needs three linear arrays instead of the four linear arrays required by JDS. Specifically, the data is aligned in such a way that the permutation array used in JDS, to permute the solution vector back to the original ordering, is unnecessary. This allow us to save the memory space required to store an integer vector of length n, where n stands for the number of columns in the sparse matrix A. This storage saving reaches, for the selection of matrices used in this work, from 14% up to 45% of the number of non-zero values of the sparse matrices. We present a case study of a 6×6 sparse matrix to show the data structures and the algorithm to compute Ax=y using the TJDS format.     

Efficient Decomposition of Associative Algebras over Finite Fields

We present new, efficient algorithms for some fundamental computations with finite-dimensional (but not necessarily commutative) associative algebras over finite fields. For a semisimple algebra A we show how to compute a complete Wedderburn decomposition of A as a direct sum of simple algebras, an isomorphism between each simple component and a full matrix algebra, and a basis for the centre of A. If A is given by a generating set of matrices inF^m × m, then our algorithm requires aboutO (m³) operations inF, in addition to the cost of factoring a polynomial inF[ x ] of degree O(m), and the cost of generating a small number of random elements from A. We also show how to compute a complete set of orthogonal primitive idempotents in any associative algebra over a finite field in this same time.     

On Minimum Witnesses for Boolean Matrix Multiplication

Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O(n ^2.575) time or in O(n ²+mnlog(n ²/m)/log² n) time. We present a new algorithm for this problem. Our algorithm runs either in time $$\tilde{O}\bigl(n^{\frac{3}{4-\omega}}m^{1-\frac{1}{4-\omega }}\bigr) $$ where ω<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time $$O\bigl(n^{1.939}m^{0.318}\bigr). $$ In particular, if ω?1<α<2 where m=n ^α , the new algorithm is faster than both of the aforementioned algorithms.     

On Space Efficient Two Dimensional Range Minimum Data Structures

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m⋅n, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1≤c≤N. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog ² c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(N⋅min {m,log n}) bits with O(1) query time, assuming m≤n. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.     

Approximation algorithms for the bandwidth minimization problem for a large class of trees

We present approximation algorithms for the bandwidth minimization problem (BMP) for a large class of trees. The BMP is NP-hard, even for trees of maximum node degree 3. The problem finds applications in many areas, including VLSI layout, multiprocessor scheduling, and matrix processing, and has been studied for both graphs and matrices. We study the problem on trees having the following property: given any tree nodev, the depth difference of any two nonempty subtrees rooted atv is bounded by a constantk. We call such treesh(k)trees orgeneralized height-balanced (GHB)trees. The above definition extends the class of balanced trees to trees with depthd=Θ(\N\). For any tree in the above defined class, anO (logd) times optimal algorithm is presented. Furthermore, we extend the application of the algorithm to trees that simulate theh(k) property, which we callh(k)-like trees, and also provide intuitive ideas for an approximation algorithm for general trees.