Central limit theorem for quadratic forms for sparse tables

Sufficient conditions for asymptotic normality for quadratic forms in {n_t − np_t} are given, where {n_t} are the observed counts with expected cell means {np_t}. The main result is used to derive asymptotic distributions of many statistics including the Pearson's chi-square.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

Exponential sums and prime divisors of sparse integers

We obtain a new lower bound on the number of prime divisors of integers whose g-ary expansion contains a fixed number of nonzero digits.      

THE RELATIONSHIP BETWEEN THE SPARSE SYMMETRIC BROYDEN METHOD AND THE M-TIME SECANT-LIKE MULTI-PROJECTION METHOD

In this paper, we discuss the relationship between the sparse symmetric Broyden （SPSB） method [1, 2] and m-time secant-like multi-projection （SMP） method [3] and prove that when m goes to infinity, the SMP method is corresponding to the SPSB method.     

Asymptotic Convergence of Conjugate Gradient Methods for the Partial Symmetric Eigenproblem

Recently an efficient method (DACG) for the partial solution of the symmetric generalized eigenproblem A x = δB x has been developed, based on the conjugate gradient (CG) minimization of the Rayleigh quotient over successive deflated subspaces of decreasing size. The present paper provides a numerical analysis of the asymptotic convergence rate ρ_j of DACG in the calculation of the eigenpair λ_j, u _j, when the scheme is preconditioned with A⁻¹. It is shown that, when the search direction are A-conjugate, ρ_j is well approximated by 4/ξ_j, where ξ_j is the Hessian condition number of a Rayleigh quotient defined in appropriate oblique complements of the space spanned by the leftmost eigenvectors u ₁, u ₂,…, u _j−1 already calculated. It is also shown that 1/ξ_j is equal to the relative separation between the eigenvalue λ_j currently sought and the next higher one λ_j+1 and the next higher one λ_{j + 1}. A modification of DACG (MDACG) is studied, which involves a new set of CG search directions which are made M-conjugate, with M-conjugate, with M-conjugate, with M a matrix approximating the Hessian. By distinction, MDACG has an asymptotic rate of convergence which appears to be inversely proportional to the square root of ξ_j, in complete agreement with the theoretical results known for the CG solution to linear systems. © 1997 by John Wiley & Sons, Ltd.     

M-TIMES SECANT-LIKE MULTI-PROJCTION METHOD FOR SPARSE MINIMIZATION PROBLEM

M-TIMES SECANT-LIKE MULTI-PROJCTION METHOD FOR SPARSE MINIMIZATION PROBLEM@林正华 @宋岱才 @赵立芹~~