Computing Row and Column Counts for Sparse QR and LU Factorization

We present algorithms to determine the number of nonzeros in each row and column of the factors of a sparse matrix, for both the QR factorization and the LU factorization with partial pivoting. The algorithms use only the nonzero structure of the input matrix, and run in time nearly linear in the number of nonzeros in that matrix. They may be used to set up data structures or schedule parallel operations in advance of the numerical factorization.The row and column counts we compute are upper bounds on the actual counts. If the input matrix is strong Hall and there is no coincidental numerical cancellation, the counts are exact for QR factorization and are the tightest bounds possible for LU factorization.These algorithms are based on our earlier work on computing row and column counts for sparse Cholesky factorization, plus an efficient method to compute the column elimination tree of a sparse matrix without explicitly forming the product of the matrix and its transpose.This revised version was published online in October 2005 with corrections to the Cover Date.     

Distance Geometry Optimization for Protein Structures

We study the performance of the dgsol code for the solution of distance geometry problems with lower and upper bounds on distance constraints. The dgsol code uses only a sparse set of distance constraints, while other algorithms tend to work with a dense set of constraints either by imposing additional bounds or by deducing bounds from the given bounds. Our computational results show that protein structures can be determined by solving a distance geometry problem with dgsol and that the approach based on dgsol is significantly more reliable and efficient than multi-starts with an optimization code.     

Automorphism groups of compact bordered Klein surfaces with invariant subsets

In this work we get upper bounds for the order of a group of automorphisms of a compact bordered Klein surface S of algebraic genus greater than 1. These bounds depend on the algebraic genus of S and on the cardinals of finite subsets of S which are invariant under the action of the group. We use our results to obtain upper bounds for the order of a group of automorphism whose action on the set of connected components of the boundary of S is not transitive. The bounds obtained this way depend only on the algebraic genus of S. The author is partially supported by the European Network RAAG HPRN-CT-2001-00271 and the Spanish GAAR DGICYT BFM2002-04797.     

Sharp bounds on distance spectral radius of graphs

Let D(G) denote the distance matrix of a connected graph G. The largest eigenvalue of D(G) is called the distance spectral radius of a graph G, denoted by ?(G). In this article, we give sharp upper and lower bounds for the distance spectral radius and characterize those graphs for which these bounds are best possible.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

矩阵Hadamard积和Fan积的特征值界的一些新估计式

本文研究了非奇异M-矩阵A与B的Fan积的最小特征值下界和非负矩阵A与B的Hadamard积 的谱半径上界的估计问题.利用Brauer定理,得到了一些只依赖于矩阵的元素且易于计算的新估计式,改进 了文献[4]现有的一些结果.     

Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. The independence number α is the maximum cardinality of an independent set of G. A series of best possible lower and upper bounds on α and some other common invariants of G are obtained by the system AGX 2, and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number.     

Finite modules over non-semisimple group rings

LetG be a fixed graph and letX _G be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofX _G which are best possible up to a logarithmic factor in the exponent. Our argument relies on an extension of Alon’s result about the maximum number of copies ofG in a graph with a given number of edges. Similar bounds are proved for the random graphG(n, M) too. Research of the second author supported by KBN grant 2 P03A 027 22. Research of the third author supported by KBN grant 2 P03A 15 23.     

Generalized Christoffel functions and error of positive quadrature

The author gives some upper and lower bounds for the generalized Christoffel functions related to a Ditzian-Totik generalized weight. As an application, an error estimate of Gauss quadrature formula inL ₁-weighted norm is derived.Dedicated to Prof. Luigi Gatteschi on the occasion of his 70th birthdayWork sponsored by MURST 40%.     

Transposition invariant string matching

Given strings A=a₁a₂…a_m and B=b₁b₂…b_n over an alphabet , where is some numerical universe closed under addition and subtraction, and a distance function d(A,B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is , where A+t=(a₁+t)(a₂+t)…(a_m+t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, including Hamming distance, longest common subsequence (LCS), Levenshtein distance, and their versions where the exact matching condition is replaced by an approximate one. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance, and for some we achieve these upper bounds. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems, and its connection with multidimensional range-minimum search. As a byproduct, we give improved sparse dynamic programming algorithms to compute LCS and Levenshtein distance.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

A computational study of graph partitioning

LetG = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node setN intok disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.Corresponding author.     

Bounds on the sizes of constant weight covering codes

Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.Part of this work was done while the first and third authors were visiting Bellcore. The third author was supported in part by National Science Foundation under grant NCR-8905052. Part of this work was presented in the Coding and Quantization Workshop at Rutgers University, NJ, October 1992.     

Maximal and minimal entry in the principal eigenvector for the distance matrix of a graph

Let G=(V,E) be a simple, connected and undirected graph with vertex set V(G) and edge set E(G). Also let D(G) be the distance matrix of a graph G (Jane?i? et al., 2007) [13]. Here we obtain Nordhaus–Gaddum-type result for the spectral radius of distance matrix of a graph.A sharp upper bound on the maximal entry in the principal eigenvector of an adjacency matrix and signless Laplacian matrix of a simple, connected and undirected graph are investigated in Das (2009) [4] and Papendieck and Recht (2000) [15]. Generally, an upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries and without zero diagonal entries are investigated in Zhao and Hong (2002) [21] and Das (2009) [4], respectively. In this paper, we obtain an upper bound on minimal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs. Moreover, we present the lower and upper bounds on maximal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs.     

Height-analysis ofk-dimensional leaf and node height-balanced trees: A new approach

A new general approach is proposed for the height-analysis ofk-dimensional leaf and node height-balanced trees which is expected to be useful for such analysis of other neighbor-supported balanced multidimensional trees as well. The approach leads to upper bounds which are the same as the known upper bounds for the corresponding 1-dimensional trees, to within an additive term.This research is partially supported by a grant from the College of Business Administration, Georgia State University, Atlanta, Georgia.Actually a variant calledalmost 2-dimensional leaf AVL-trees is introduced in order to facilitate the derivation of an upper bound for the height of these trees which is within an additive term to the bound for such 1-dimensional trees.