Linear rank and corank preserving maps on (H) and an application to *-semigroup isomorphisms of operator ideals

We characterize linear rank-k nonincreasing, rank-k preserving, and corank-k preserving maps on B(H), the algebra of all bounded linear operators on the Hilbert space H. This unifies and extends finite-dimensional results and results on linear rank-1 non-increasing and rank-1 preserving maps in the infinite-dimensional case. We conclude with an application to *-semigroup isomorphisms of operator ideals.     

A systolic generation of combinations

A parallel algorithm for generating all combinations ofm (m fixed) items out of anyn given items in lexicographic order is presented. The computational model is a linear systolic array consisting ofm identical processing elements. This algorithm requires {ie23-1} time-steps for the {ie23-2} combinations, that is, one output at each time-step. Since all processing elements perform the same program, it is suitable for VLSI implementation. Based on mathematical induction, such an algorithm is proved to be correct.     

Complexity reduction of least squares problems involving special vandermonde matrices

This paper presents a new QRD factorization of a rectangular Vandermonde matrix for a special point distribution, including the symmetric case, based on ak-dimensional block decomposition of the matrix and some properties of the Kronecker product. The computational reduction factor with respect to any QR method isk ², in the general case, and 4 in the symmetric one. By the resulting matrix factorization, new formulas are devised for the least squares system solution, whose implementation produces an algorithm of reduced computational cost and computer storage. Finally the perturbation bounds of this new factorization are devised.     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

AVLSI partition algorithm

A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.     

Rank-k modification methods for recursive least squares problems

In least squares problems, it is often desired to solve the same problem repeatedly but with several rows of the data either added, deleted, or both. Methods for quickly solving a problem after adding or deleting one row of data at a time are known. In this paper we introduce fundamental rank-k updating and downdating methods and show how extensions of rank-1 downdating methods based on LINPACK, Corrected Semi-Normal Equations (CSNE), and Gram-Schmidt factorizations, as well as new rank-k downdating methods, can all be derived from these fundamental results. We then analyze the cost of each new algorithm and make comparisons tok applications of the corresponding rank-1 algorithms. We provide experimental results comparing the numerical accuracy of the various algorithms, paying particular attention to the downdating methods, due to their potential numerical difficulties for ill-conditioned problems. We then discuss the computation involved for each downdating method, measured in terms of operation counts and BLAS calls. Finally, we provide serial execution timing results for these algorithms, noting preferable points for improvement and optimization. From our experiments we conclude that the Gram-Schmidt methods perform best in terms of numerical accuracy, but may be too costly for serial execution for large problems.Research supported in part by the Joint Services Electronics Program, contract no. F49620-90-C-0039.     

DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling

The importance of unsupervised clustering and topic modeling is well recognized with ever-increasing volumes of text data available from numerous sources. Nonnegative matrix factorization (NMF) has proven to be a successful method for cluster and topic discovery in unlabeled data sets. In this paper, we propose a fast algorithm for computing NMF using a divide-and-conquer strategy, called DC-NMF. Given an input matrix where the columns represent data items, we build a binary tree structure of the data items using a recently-proposed efficient algorithm for computing rank-2 NMF, and then gather information from the tree to initialize the rank-k NMF, which needs only a few iterations to reach a desired solution. We also investigate various criteria for selecting the node to split when growing the tree. We demonstrate the scalability of our algorithm for computing general rank-k NMF as well as its effectiveness in clustering and topic modeling for large-scale text data sets, by comparing it to other frequently utilized state-of-the-art algorithms. The value of the proposed approach lies in the highly efficient and accurate method for initializing rank-k NMF and the scalability achieved from the divide-and-conquer approach of the algorithm and properties of rank-2 NMF. In summary, we present efficient tools for analyzing large-scale data sets, and techniques that can be generalized to many other data analytics problem domains along with an open-source software library called SmallK.     

A new algorithm for special Vandermonde systems

In this paper a new algorithm for solving special Vandermonde systems is presented, useful when then points defining the matrix are thek th roots ofm complex numbers (n=km); if they are real and positive andn=2m, the usual case of real points symmetrically ranged around zero is obtained. The algorithm is based on an inverse matrix formulation by means of the Kronecker product and is particularly suitable for parallel implementation. Its computational complexity is analysed and compared both in the sequential and parallel formulation.     

A note on the height of thekth element in a heap

De Graaf and Kosters have studied the expected height of thekth element in a heap. They conjecture that, for largek, this is asymptotic to log₂ k + 0.72 .... We show that the height of thekth element is related to the depth of insertion in a digital search tree, and use this relation to prove their conjecture.This research was supported by grant FONDECYT (Chile) 91-1252.     

Bin packing: On optimizing the number of pieces packed

We consider bin-packing variations related to the well-studied problem of maximizing the total number of pieces packed into a fixed set of bins. We show that, when the objective is to minimize the total number of pieces packed subject to the constraint that no unpacked piece will fit, no polynomial-time relative approximation algorithm exists (unless, of course,P=NP). That is, we prove that it isNP-hard to guarantee packing no more than a constant multiple of the optimal number of pieces, for any constant. This appears to be the first bin-packing problem for which this property has been demonstrated. Furthermore, this result also holds for the allied packing variant which seeks to minimize the maximum number of pieces packed in any single bin. We find the situation to be markedly better for the problem of maximizing the minimum number of pieces in any bin. If all bins possess the same capacity, we prove that the familiar SPF rule is an absolute approximation algorithm with additive constant 1, and can therefore be regarded as a best possible heuristic. For the more general and difficult case in which bin capacities may differ, it turns out that SPF fails to qualify as even a relative approximation algorithm. However, we devise an implementation of the well-known FFD heuristic, which we show to be a relative approximation algorithm, yielding a worst-case performance ratio of 1/2 with additive constant 0. Moreover, we prove that (unlessP=NP) no polynomial-time algorithm can guarantee a higher ratio without sacrificing the additive constant.This author's research is supported in part by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

Parallel generation of permutations and combinations

In this paper we will present a parallel algorithm to generate the permutations of at mostk out ofn objects. The architecture consists of a linear processor array and a selector. When one single processor array is available, a parallel algorithm to generate permutations is presented which achieves the best possible speedup for any givenk. Also, this algorithm can easily be modified to generate combinations. When multiple processor arrays are available, a parallel scheme is proposed to speed up the generation by fully utilizing these processor arrays. The degree of parallelism is related to the number of available processor arrays.     

Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection

A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE ^k ,k>1, projects the given point setS onto thex-axis. For each pointq S a nearest neighbor inS under anyL _p -metric (1 p ) is found by sweeping fromq into two opposite directions along thex-axis. If _q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2 _q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] ^k in (n ^2–1/k ) expected time, while its worst-case performance is (n ²).     

The effect of table expansion on the program complexity of perfect hash functions

It has been shown by various researchers that designing a perfect hashing function for a fixed set ofn elements requires (n) bits in the worst case. A possible relaxation of this scheme is to partition the set into pages, and design a hash function which maps keys to page addresses, requiring subsequent binary search of the page. We have shown elsewhere that (nk/2 ^k+1)(1 +o(1)) bits are necessary and sufficient to describe such a hash function where the pages are of size 2 ^k . In this paper we examine the additional scheme of expanding the address space of the table, which does substantially improve the hash function complexity of perfect hashing, and show that in contrast, it does not reduce the hash function complexity of the paging scheme.Research supported by NSF Grant CCR-9017125 and by a grant from Texas Instruments.     

A linear systolic algorithm for the connected component problem

A linear systolic algorithm is proposed for the connected component problem. Given an undirected graph withn vertices,m edges, andp connected components, the proposed algorithm uses (n –p + 1) cells pipelined together to figure out, in (m + 3(n –p) + 2) systolic cycles, which component each vertex belongs to.This research was supported by the National Science Council of the Republic of China under the Contract NSC77-0408-E007-01.     

Computable eigenvalue bounds for rank-k perturbations

We investigate lower bounds for the eigenvalues of perturbations of matrices. In the footsteps of Weyl and Ipsen & Nadler, we develop approximating matrices whose eigenvalues are lower bounds for the eigenvalues of the perturbed matrix. The number of available eigenvalues and eigenvectors of the original matrix determines how close those approximations can be, and, if the perturbation is of low rank, such bounds are relatively inexpensive to obtain. Moreover, because the process need not be restricted to the eigenvalues of perturbed matrices, lower bounds for eigenvalues of bordered diagonal matrices as well as for singular values of rank-k perturbations and other updates of n×m matrices are given.     

Selection on rectangular meshes with multiple broadcasting

One of the fundamental algorithmic problems in computer science involves selecting thekth smallest element in a setS ofn elements. In this paper we present a fast selection algorithm which runs inO(n ^1/8 logn) time on a mesh with multiple broadcasting of sizen ^3/8 ×n ^5/8. Our result shows that, just like semigroup computations, selection can be done much faster on a suitably chosen rectangular mesh than on square meshes. We also show that if every processor can storen ^1/9 items, then our selection algorithm runs inO(n ^1/9 logn) time on a mesh with multiple broadcasting of sizen ^1/3 ×n ^5/9.Work supported by NASA under grant NCC1-99.This author was partly supported by NSF grant CCR-8009996.     

Exploring the constrained maximum edge-weight connected graph problem

Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

An alternative to the Ritz pairs with the EN subspace method

In this note we define EN subspaces by using the Eirola-Nevanlinna algorithm for solving a linear system. We compare this construction with the Arnoldi method for generating Krylov subspaces and computing eigenvalue approximations. Further, we compute Ritz pairs by restricting the updated preconditionerH _k of the EN algorithm to the generated EN subspaces.