Search

Recently, Smooth Rank Function (SRF) is proposed for matrix completion problem. The main idea of this algorithm is based on a continuous and differentiable approximation of the rank function. However, it need to deal with singular value decomposition of matrix in each iteration, which consumes much time for large matrix. In this paper, by utilizing the tri-factorization of matrix, a fast matrix completion method based on SRF is proposed. Then, based on our fast matrix completion method, a rank adaptive smooth rank function approximation is presented with appropriate rank estimation. We mathematically prove the convergence of the proposed method. Experimental results show that our proposed method improves the running time significantly. Furthermore, our proposed method outperforms other existing matrix completion approaches in most cases. [ABSTRACT FROM AUTHOR]

Solving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time-consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For this reason, optimizing their performance on modern architectures is critical. The preprocessing steps of sparse direct solvers|ordering and block-symbolic factorization|are two major steps that lead to a reduced amount of computation and memory and to a better task granularity to reach a good level of performance when using BLAS kernels. With the advent of GPUs, the granularity of the block computation has become more important than ever. In this paper, we present a reordering strategy that increases this block granularity. This strategy relies on block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. We integrate this algorithm in the PaStiX solver and show an important reduction of the number of off-diagonal blocks on a large spectrum of matrices. This improvement leads to an increase in efficiency of up to 20% on GPUs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of blind identification of a convolutive multiple-input-multiple-output (MIMO) system with No outputs and Ni inputs. While many methods have been proposed to blindly identify convolutive MIMO systems with No ≥ Ni (overdetermined), very scarce results exist for the case of No < Ni (underdetermined), all of which refer to systems that either have some special structure or special No and Ni values. In this paper, we show that, as long as min(No, Ni) ≥ 2, independent of whether the system is overdetermined or underdetermined, we can always find the appropriate order of statistics that guarantees identifiability of the system response within trivial ambiguities. We also propose an algorithm to reach the solution, that consists of parallel factorization (PARAFAC) of a K-way tensor containing K th-order statistics of the system outputs, followed by an iterative scheme. For a certain order of statistics K, we provide the description of the class of identifiable MIMO systems. We also show that this class can be expanded by applying PARAFAC decomposition to a pair of tensors instead of one tensor. The proposed approach constitutes a novel scheme for estimation of underdetermined systems, and improves over existing approaches for overdetermined systems. [ABSTRACT FROM AUTHOR]

This paper describes a family of Nested Factorization (NF) algorithms, which are used as preconditioners in the iterative solution of sparse linear systems arising in discretization of elliptic or parabolic PDE in 2D and 3D. Nested factorization differs from the widely used incomplete LU/Cholesky factorizations in that the preconditioning matrix in NF is not formed strictly from upper and lower factors. Instead, NF exploits the nested triangular structure of the original matrix by defining the preconditioner matrix as a sequence of level matrices with the diagonal matrix on the lowest level. We present the variants of NF and Generalized NF (GNF) for systems arising in regular 7-point stencil and block 7-point stencil discretizations of PDE on structured grids, respectively. We also introduce a variant of Nested Factorization named UNF, applied to matrices arising in discretization of PDE on unstructured grid. This variant is based on a special reordering technique which recovers a multi-level structure for a general sparse matrix. Numerical results presented in the paper show that nested factorization algorithms give faster convergence and require less memory than ILU-type methods for sets of test matrices. [ABSTRACT FROM AUTHOR]

We present a preconditioning technique, called support-graph preconditioning, and use it to analyze two classes of preconditioners. The technique was first described in a talk by Pravin Vaidya, who did not formally publish his results. Vaidya used the technique to devise and analyze a class of novel preconditioners. The technique was later extended by Gremban and Miller, who used it in the development and analysis of yet another class of new preconditioners. This paper extends the technique further and uses it to analyze a class of existing preconditioners, modified incomplete Cholesky. The paper also contains a presentation of Vaidya's preconditioners, which was previously missing from the literature. [ABSTRACT FROM AUTHOR]

The Jacobi-Davidson (JD) algorithm is considered one of the most efficient eigensolvers currently available for non-Hermitian problems. It can be viewed as a coupled inner-outer iteration, where the inner one expands the search subspace and the outer one reduces the eigenpair residual. One of the difficulties in the JD efficient use stems from the definition of the most appropriate inner tolerance, so as to avoid useless extra work and keep the number of outer iterations under control. To this aim, the use of an efficient preconditioner for the inner iterative solver is of paramount importance. The present paper describes a fresh implementation of the JD algorithm with controlled inner iterations and block factorized sparse approximate inverse preconditioning for non-Hermitian eigenproblems in a parallel computational environment. The algorithm performance is investigated by comparison with a freely available software package such as SLEPc. The results show that combining the inner tolerance control with an efficient preconditioning technique can allow for a significant improvement of the JD performance, preserving a good scalability. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The solution of large sparse linear systems arises in many applications, such as computational fluid dynamics and oil reservoir simulation. In realistic cases the matrices are often so large that they require large scale distributed parallel computing to obtain the solution of interest in a reasonable time. In this paper we discuss the design and implementation of the AmgX library, which provides drop-in GPU acceleration of distributed algebraic multigrid (AMG) and preconditioned iterative methods. The AmgX library implements both classical and aggregation-based AMG methods with different selector and interpolation strategies, along with a variety of smoothers and preconditioners, including block-Jacobi, Gauss-Seidel, and incomplete-LU factorization. The library contains many of the standard and flexible preconditioned Krylov subspace iterative methods, which can be combined with any of the available multigrid methods or simpler preconditioners. The parallelism in the aggregation scheme exploits parallel graph matching techniques, while the smoothers and preconditioners often rely on parallel graph coloring algorithms. The AMG algorithm implemented in the AmgX library achieves 2-5× speedup on a single GPU against a competitive implementation on the CPU. As will be shown in the numerical experiments section, both setup and solve phases scale well across multiple nodes, sustaining this performance advantage. [ABSTRACT FROM AUTHOR]

The matrix separation problem aims to separate a low-rank matrix and a sparse matrix from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications. Nuclear-norm minimization models have been proposed for matrix separation and proved to yield exact separations under suitable conditions. These models, however, typically require the calculation of a full or partial singular value decomposition at every iteration that can become increasingly costly as matrix dimensions and rank grow. To improve scalability, in this paper, we propose and investigate an alternative approach based on solving a non-convex, low-rank factorization model by an augmented Lagrangian alternating direction method. Numerical studies indicate that the effectiveness of the proposed model is limited to problems where the sparse matrix does not dominate the low-rank one in magnitude, though this limitation can be alleviated by certain data pre-processing techniques. On the other hand, extensive numerical results show that, within its applicability range, the proposed method in general has a much faster solution speed than nuclear-norm minimization algorithms and often provides better recoverability. [ABSTRACT FROM PUBLISHER]

Abstract: In recent years, robust subspace clustering is an important unsupervised clustering problem in machine learning and computer vision communities. The recently proposed spectral clustering based approach, called low-rank representation (LRR), yields an optimal solution for the case of independent subspaces and partially corrupted data. However, it has to be solved iteratively and involves singular value decomposition (SVD) at each iteration, and then suffers from high computation cost of multiple SVDs. In this paper, we propose an efficient matrix tri-factorization (MTF) approach with a positive semidefinite (PSD) constraint to approximate the original nuclear norm minimization (NNM) problem and mitigate the computation cost of performing SVDs. Specially, we introduce a matrix tri-factorization idea into the original low-rank representation framework, and then convert it into a small scale matrix nuclear norm minimization problem. Finally, we establish an alternating direction method (ADM) based algorithm to efficiently solve the proposed problem. Experimental results on a variety of synthetic and real-world data sets validate the efficiency, robustness and effectiveness of the proposed MTF approach comparing with the state-of-the-art algorithms. [Copyright &y& Elsevier]

In this paper, the new pivoting strategy named boundedly partial pivoting is presented in the process of the incomplete LDLT factorization, based on the maximum weighted matchings in the preprocessing of solving a symmetric indefinite linear system. This new pivoting method is acquired by changing the tri-diagonal pivoting algorithm, and none of permutations of rows and columns are needed. Meanwhile, the lower triangular factor L is bounded. Numerical results demonstrate that the newly proposed pivoting strategy can extend the scope of applications of the LDLT preconditioner, compared with the tri-diagonal pivoting. Moreover, almost the same results are obtained or our boundedly partial pivoting is more efficient with respect to the iteration speed, when both the tri-diagonal pivoting and the boundedly partial pivoting are applicable to incomplete LDLT factorization. [ABSTRACT FROM AUTHOR]

Abstract: Rank-one residue iteration (RRI) is a recently developed block coordinate method for nonnegative matrix factorization (NMF). Numerical results show that the decomposed matrices generated by RRI method may have several columns, which are zero vectors. In this paper, by studying two special kinds of quadratic programming, we develop two block coordinate methods for NMF, rank-two residue iteration (RTRI) method and rank-two modified residue iteration (RTMRI) method. In the two algorithms, the exact solution of the subproblem can be obtained directly. We also provide that the consequence generated by our proposed algorithms can converge to a stationary point. Numerical results show that the RTRI method and the RTMRI method can yield better solutions, especially RTMRI method can remedy the limitation of the RRI method. [Copyright &y& Elsevier]

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large-scale problems. In this paper, we have developed an efficient iterative solver for solving large-scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection-diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: Solving a sparse system of linear equations is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix 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) 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 to , where is the order of the matrix and 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. [ABSTRACT FROM AUTHOR]

Abstract: Natural aquifers are complex media and contain heterogeneous structures. This paper introduces a new algorithm to simulate flow fluid in such complex media. A parallel version of the method is released, and two well-known sparse linear solvers, based, respectively, on a multifrontal Cholesky factorization and an iterative structured multigrid method, are tested. The mixed finite element (MFE) method is used to discretize Darcy’s equation. The efficiency of the algorithm proposed is shown in different numerical examples. [Copyright &y& Elsevier]

Abstract: In this paper, a method via sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix is proposed. The resulting factorized sparse approximate inverse is used as a preconditioner for solving symmetric positive definite linear systems of equations by using the preconditioned conjugate gradient algorithm. Some numerical experiments on test matrices from the Harwell–Boeing collection for comparing the numerical performance of the presented method with one available well-known algorithm are also given. [Copyright &y& Elsevier]

In this paper we propose a new projection method to solve large-scale continuoustime Lyapunov matrix equations. The new approach projects the problem onto a much smaller approximation space, generated as a combination of Krylov subspaces in A and A-1. The reduced problem is then solved by means of a direct Lyapunov scheme based on matrix factorizations. The reported numerical results show the competitiveness of the new method, compared to a state-of-the-art approach based on the factorized alternating direction implicit iteration. [ABSTRACT FROM AUTHOR]

A new circuit analysis method, named SPICE-accurate iterative linear-centric analysis (SILCA), is proposed for the efficient and accurate time-domain simulation of deep submicron very large scale integrated (VLSI) circuits with strong parasitic couplings. SILCA consists of two key linear-centric techniques applied to time-domain nonlinear circuit simulation. For numerical integration, explicit-formula substitution and iterative-formula transformation are presented to convert implicit variable time-step integration to fixed leading coefficient (FLC) variable time-step integration. This paper characterizes both convergence and stability properties of the resulting FLC integration formulae. For nonlinear iteration, a successive variable chord (SVC) method is used as an alternative to the Newton-Raphson method. Further, the low-rank update technique is implemented for fast LU factorization. With these techniques, the number and cost of required LU factorizations are reduced dramatically. Experimental results on nonlinear circuits coupled with substrate and power/ground networks have demonstrated that SILCA achieves more than an order of magnitude speedup over SPICE3 in terms of both the cost of LU factarization and the overall CPU time. SILCA is suitable for efficient SPICE-like time-domain simulation of parasitic-coupled VLSI circuits, where the number of linear parasitic elements dominates the number of nonlinear devices. [ABSTRACT FROM AUTHOR]

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. [ABSTRACT FROM AUTHOR]

Consider an incomplete Cholesky factorization of a sparse symmetric positive definite matrix. It is common practice to start with a symmetric permutation of the rows and columns of the matrix using an ordering to reduce fill in the complete Cholesky factor. Such an approach has two drawbacks. First, such an ordering is designed to reduce fill or operation counts in the complete Cholesky factor, and thus does not necessarily address the issue of controlling fill or operation counts during incomplete factorization. Second, because the ordering is determined in advance of the incomplete factorization, it is not easy to accommodate alternative pivoting sequences, for example, using numeric measures to promote stability, while taking into account their impact on fill and operation counts. In this paper, we consider an alternative approach that interleaves ordering with numeric computation in an incomplete Cholesky factorization. Such an interleaved scheme controls fill and operation counts. It also allows the incorporation of some limited, pivot selection strategies for stability. We demonstrate through experiments that our interleaved minimum-degree approach leads to fewer failures during incomplete factorization and improved convergence when the incomplete factor is used as a preconditioner for the conjugate gradient method. We conjecture that the improvements in the quality of preconditioning arise from the ability of our method to generate better approximations to the complete factor. [ABSTRACT FROM AUTHOR]

We consider methods, both direct and iterative, for solving an R-linear system Mz + M#&zoline; = b in Cn with a pair of matrices M,M# ∈ C,n × n and a vector b ∈ Cn. Algorithms that avoid formulating the problem as an equivalent real linear system in R2n are introduced. Conversely, this implies that real linear systems in R2n can be solved with the methods proposed in this paper. Our study is motivated by Krylov subspace iterations, which when used with the real formulation can be disastrous in the standard linear case. Related matrix analysis and spectral theory are developed. [ABSTRACT FROM AUTHOR]

This paper describes a technique for constructing robust preconditioners for the CGLS method applied to the solution of large and sparse least squares problems. The algorithm computes an incomplete LDLT factorization of the normal equations matrix without the need to form the normal matrix itself. The preconditioner is reliable (pivot breakdowns cannot occur) and has low intermediate storage requirements. Numerical experiments illustrating the performance of the preconditioner are presented. A comparison with incomplete QR preconditioners is also included. [ABSTRACT FROM AUTHOR]