The Experts below are selected from a list of 4803 Experts worldwide ranked by ideXlab platform
Juan J Navarro - One of the best experts on this subject based on the ideXlab platform.
-
PARA - Optimization of a statically partitioned hypermatrix sparse Cholesky Factorization
Applied Parallel Computing. State of the Art in Scientific Computing, 2006Co-Authors: Jose R Herrero, Juan J NavarroAbstract:The sparse Cholesky Factorization of some large matrices can require a two dimensional partitioning of the matrix. The sparse hypermatrix storage scheme produces a recursive 2D partitioning of a sparse matrix. The subblocks are stored as dense matrices so BLAS3 routines can be used. However, since we are dealing with sparse matrices some zeros may be stored in those dense blocks. The overhead introduced by the operations on zeros can become large and considerably degrade performance. In this paper we present an improvement to our sequential in-core implementation of a sparse Cholesky Factorization based on a hypermatrix storage structure. We compare its performance with several codes and analyze the results.
-
Optimization of a statically partitioned hypermatrix sparse Cholesky Factorization
Lecture Notes in Computer Science, 2006Co-Authors: Jose R Herrero, Juan J NavarroAbstract:The sparse Cholesky Factorization of some large matrices can require a two dimensional partitioning of the matrix. The sparse hypermatrix storage scheme produces a recursive 2D partitioning of a sparse matrix. The subblocks are stored as dense matrices so BLAS3 routines can be used. However, since we are dealing with sparse matrices some zeros may be stored in those dense blocks. The overhead introduced by the operations on zeros can become large and considerably degrade performance. In this paper we present an improvement to our sequential in-core implementation of a sparse Cholesky Factorization based on a hypermatrix storage structure. We compare its performance with several codes and analyze the results.
-
improving performance of hypermatrix Cholesky Factorization
European Conference on Parallel Processing, 2003Co-Authors: Jose R Herrero, Juan J NavarroAbstract:This paper shows how a sparse hypermatrix Cholesky Factorization can be improved. This is accomplished by means of efficient codes which operate on very small dense matrices. Different matrix sizes or target platforms may require different codes to obtain good performance. We write a set of codes for each matrix operation using different loop orders and unroll factors. Then, for each matrix size, we automatically compile each code fixing matrix leading dimensions and loop sizes, run the resulting executable and keep its Mflops. The best combination is then used to produce the object introduced in a library. Thus, a routine for each desired matrix size is available from the library. The large overhead incurred by the hypermatrix Cholesky Factorization of sparse matrices can therefore be lessened by reducing the block size when those routines are used. Using the routines, e.g. matrix multiplication, in our small matrix library produced important speed-ups in our sparse Cholesky code.
-
Euro-Par - Improving Performance of Hypermatrix Cholesky Factorization
Euro-Par 2003 Parallel Processing, 2003Co-Authors: Jose R Herrero, Juan J NavarroAbstract:This paper shows how a sparse hypermatrix Cholesky Factorization can be improved. This is accomplished by means of efficient codes which operate on very small dense matrices. Different matrix sizes or target platforms may require different codes to obtain good performance. We write a set of codes for each matrix operation using different loop orders and unroll factors. Then, for each matrix size, we automatically compile each code fixing matrix leading dimensions and loop sizes, run the resulting executable and keep its Mflops. The best combination is then used to produce the object introduced in a library. Thus, a routine for each desired matrix size is available from the library. The large overhead incurred by the hypermatrix Cholesky Factorization of sparse matrices can therefore be lessened by reducing the block size when those routines are used. Using the routines, e.g. matrix multiplication, in our small matrix library produced important speed-ups in our sparse Cholesky code.
Jack Dongarra - One of the best experts on this subject based on the ideXlab platform.
-
Implementation and Tuning of Batched Cholesky Factorization and Solve for NVIDIA GPUs
IEEE Transactions on Parallel and Distributed Systems, 2016Co-Authors: Jakub Kurzak, Hartwig Anzt, Mark Gates, Jack DongarraAbstract:Many problems in engineering and scientific computing require the solution of a large number of small systems of linear equations. Due to their high processing power, Graphics Processing Units became an attractive target for this class of problems, and routines based on the LU and the QR Factorization have been provided by NVIDIA in the cuBLAS library. This work addresses the situation where the systems of equations are symmetric positive definite. The paper describes the implementation and tuning of the kernels for the Cholesky Factorization and the forward and backward substitution. Targeted workloads involve the solution of thousands of linear systems of the same size, where the focus is on matrix dimensions from 5 by 5 to 100 by 100. Due to the lack of a cuBLAS Cholesky Factorization, execution rates of cuBLAS LU and cuBLAS QR are used for comparison against the proposed Cholesky Factorization in this work. Execution rates of forward and backward substitution routines are compared to equivalent cuBLAS routines. Comparisons against optimized multicore implementations are also presented. Superior performance is reached in all cases.
-
a fast batched Cholesky Factorization on a gpu
International Conference on Parallel Processing, 2014Co-Authors: Tingxing Dong, Azzam Haidar, Stanimire Tomov, Jack DongarraAbstract:Currently, state of the art libraries, like MAGMA, focus on very large linear algebra problems, while solving many small independent problems, which is usually referred to as batched problems, is not given adequate attention. In this paper, we proposed a batched Cholesky Factorization on a GPU. Three algorithms -- non-blocked, blocked, and recursive blocked -- were examined. The left-looking version of the Cholesky Factorization is used to factorize the panel, and the right-looking Cholesky version is used to update the trailing matrix in the recursive blocked algorithm. Our batched Cholesky achieves up to 1.8× speedup compared to the optimized parallel implementation in the MKL library on two sockets of Intel Sandy Bridge CPUs. Further, we use the new routines to develop a single Cholesky Factorization solver which targets large matrix sizes. Our approach differs from MAGMA by having an entirely GPU implementation where both the panel Factorization and the trailing matrix updates are on the GPU. Such an implementation does not depend on the speed of the CPU. Compared to the MAGMA library, our full GPU solution achieves 85% of the hybrid MAGMA performance which uses 16 Sandy Bridge cores, in addition to a K40 Nvidia GPU. Moreover, we achieve 80% of the practical dgemm peak of the machine, while MAGMA achieves only 75%, and finally, in terms of energy consumption, we outperform MAGMAby 1.5× in performance-per-watt for large matrices.
-
ICPP - A Fast Batched Cholesky Factorization on a GPU
2014 43rd International Conference on Parallel Processing, 2014Co-Authors: Tingxing Dong, Azzam Haidar, Stanimire Tomov, Jack DongarraAbstract:Currently, state of the art libraries, like MAGMA, focus on very large linear algebra problems, while solving many small independent problems, which is usually referred to as batched problems, is not given adequate attention. In this paper, we proposed a batched Cholesky Factorization on a GPU. Three algorithms -- non-blocked, blocked, and recursive blocked -- were examined. The left-looking version of the Cholesky Factorization is used to factorize the panel, and the right-looking Cholesky version is used to update the trailing matrix in the recursive blocked algorithm. Our batched Cholesky achieves up to 1.8× speedup compared to the optimized parallel implementation in the MKL library on two sockets of Intel Sandy Bridge CPUs. Further, we use the new routines to develop a single Cholesky Factorization solver which targets large matrix sizes. Our approach differs from MAGMA by having an entirely GPU implementation where both the panel Factorization and the trailing matrix updates are on the GPU. Such an implementation does not depend on the speed of the CPU. Compared to the MAGMA library, our full GPU solution achieves 85% of the hybrid MAGMA performance which uses 16 Sandy Bridge cores, in addition to a K40 Nvidia GPU. Moreover, we achieve 80% of the practical dgemm peak of the machine, while MAGMA achieves only 75%, and finally, in terms of energy consumption, we outperform MAGMAby 1.5× in performance-per-watt for large matrices.
-
a scalable high performant Cholesky Factorization for multicore with gpu accelerators
IEEE International Conference on High Performance Computing Data and Analytics, 2010Co-Authors: Hatem Ltaief, Stanimire Tomov, Rajib Nath, Jack DongarraAbstract:We present a Cholesky Factorization for multicore with GPU accelerators systems. The challenges in developing scalable high performance algorithms for these emerging systems stem from their heterogeneity, massive parallelism, and the huge gap between the GPUs' compute power vs the CPU-GPU communication speed. We show an approach that is largely based on software infrastructures that have already been developed for homogeneous multicores and hybrid GPU-based computing. This results in a scalable hybrid Cholesky Factorization of unprecedented performance. In particular, using NVIDIA's Tesla S1070 (4 C1060 GPUs, each with 30 cores @1.44 GHz) connected to two dual-core AMD Opteron @1.8GHz processors, we reach up to 1.163 TFlop/s in single and up to 275 GFlop/s in double precision arithmetic. Compared with the performance of the embarrassingly parallel xGEMM over four GPUs, where no communication between GPUs are involved, our algorithm still runs at 73% and 84% for single and double precision arithmetic respectively.
Jose R Herrero - One of the best experts on this subject based on the ideXlab platform.
-
PARA - Optimization of a statically partitioned hypermatrix sparse Cholesky Factorization
Applied Parallel Computing. State of the Art in Scientific Computing, 2006Co-Authors: Jose R Herrero, Juan J NavarroAbstract:The sparse Cholesky Factorization of some large matrices can require a two dimensional partitioning of the matrix. The sparse hypermatrix storage scheme produces a recursive 2D partitioning of a sparse matrix. The subblocks are stored as dense matrices so BLAS3 routines can be used. However, since we are dealing with sparse matrices some zeros may be stored in those dense blocks. The overhead introduced by the operations on zeros can become large and considerably degrade performance. In this paper we present an improvement to our sequential in-core implementation of a sparse Cholesky Factorization based on a hypermatrix storage structure. We compare its performance with several codes and analyze the results.
-
Optimization of a statically partitioned hypermatrix sparse Cholesky Factorization
Lecture Notes in Computer Science, 2006Co-Authors: Jose R Herrero, Juan J NavarroAbstract:The sparse Cholesky Factorization of some large matrices can require a two dimensional partitioning of the matrix. The sparse hypermatrix storage scheme produces a recursive 2D partitioning of a sparse matrix. The subblocks are stored as dense matrices so BLAS3 routines can be used. However, since we are dealing with sparse matrices some zeros may be stored in those dense blocks. The overhead introduced by the operations on zeros can become large and considerably degrade performance. In this paper we present an improvement to our sequential in-core implementation of a sparse Cholesky Factorization based on a hypermatrix storage structure. We compare its performance with several codes and analyze the results.
-
improving performance of hypermatrix Cholesky Factorization
European Conference on Parallel Processing, 2003Co-Authors: Jose R Herrero, Juan J NavarroAbstract:This paper shows how a sparse hypermatrix Cholesky Factorization can be improved. This is accomplished by means of efficient codes which operate on very small dense matrices. Different matrix sizes or target platforms may require different codes to obtain good performance. We write a set of codes for each matrix operation using different loop orders and unroll factors. Then, for each matrix size, we automatically compile each code fixing matrix leading dimensions and loop sizes, run the resulting executable and keep its Mflops. The best combination is then used to produce the object introduced in a library. Thus, a routine for each desired matrix size is available from the library. The large overhead incurred by the hypermatrix Cholesky Factorization of sparse matrices can therefore be lessened by reducing the block size when those routines are used. Using the routines, e.g. matrix multiplication, in our small matrix library produced important speed-ups in our sparse Cholesky code.
-
Euro-Par - Improving Performance of Hypermatrix Cholesky Factorization
Euro-Par 2003 Parallel Processing, 2003Co-Authors: Jose R Herrero, Juan J NavarroAbstract:This paper shows how a sparse hypermatrix Cholesky Factorization can be improved. This is accomplished by means of efficient codes which operate on very small dense matrices. Different matrix sizes or target platforms may require different codes to obtain good performance. We write a set of codes for each matrix operation using different loop orders and unroll factors. Then, for each matrix size, we automatically compile each code fixing matrix leading dimensions and loop sizes, run the resulting executable and keep its Mflops. The best combination is then used to produce the object introduced in a library. Thus, a routine for each desired matrix size is available from the library. The large overhead incurred by the hypermatrix Cholesky Factorization of sparse matrices can therefore be lessened by reducing the block size when those routines are used. Using the routines, e.g. matrix multiplication, in our small matrix library produced important speed-ups in our sparse Cholesky code.
W Hagerwilliam - One of the best experts on this subject based on the ideXlab platform.
-
Row Modifications of a Sparse Cholesky Factorization
SIAM Journal on Matrix Analysis and Applications, 2005Co-Authors: A Davistimothy, W HagerwilliamAbstract:Given a sparse, symmetric positive definite matrix C and an associated sparse Cholesky Factorization LDL$\tr$, we develop sparse techniques for updating the Factorization after a symmetric modifica...
-
Multiple-Rank Modifications of a Sparse Cholesky Factorization
SIAM Journal on Matrix Analysis and Applications, 2000Co-Authors: A Davistimothy, W HagerwilliamAbstract:Given a sparse symmetric positive definite matrix $\mathbf{AA}\tr$ and an associated sparse Cholesky Factorization $\mathbf{LDL}\tr$ or $\mathbf{LL}\tr$, we develop sparse techniques for updating t...
-
Modifying a Sparse Cholesky Factorization
SIAM Journal on Matrix Analysis and Applications, 1999Co-Authors: A Davistimothy, W HagerwilliamAbstract:Given a sparse symmetric positive definite matrix ${\bf AA}^{\sf T}$ and an associated sparse Cholesky Factorization ${\bf LDL}^{\sf T}$ or ${\bf LL}^{\sf T}$, we develop sparse techniques for obta...
William W. Hager - One of the best experts on this subject based on the ideXlab platform.
-
algorithm 887 cholmod supernodal sparse Cholesky Factorization and update downdate
ACM Transactions on Mathematical Software, 2008Co-Authors: Yanqing Chen, Timothy A. Davis, William W. Hager, Sivasankaran RajamanickamAbstract:CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky Factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky Factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLABTM interfaces. It appears in MATLAB 7.2 as x = A\b when A is sparse symmetric positive definite, as well as in several other sparse matrix functions.
-
Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
ACM Transactions on Mathematical Software, 2008Co-Authors: Yanqing Chen, Timothy A. Davis, William W. Hager, Sivasankaran RajamanickamAbstract:CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky Factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky Factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLABTM interfaces. It appears in MATLAB 7.2 as x = A\b when A is sparse symmetric positive definite, as well as in several other sparse matrix functions.
-
Row Modifications of a Sparse Cholesky Factorization
SIAM Journal on Matrix Analysis and Applications, 2005Co-Authors: Timothy A. Davis, William W. HagerAbstract:Given a sparse, symmetric positive definite matrix C and an associated sparse Cholesky Factorization LDL$\tr$, we develop sparse techniques for updating the Factorization after a symmetric modification of a row and column of C. We show how the modification in the Cholesky Factorization associated with this rank-2 modification of C can be computed efficiently using a sparse rank-1 technique developed in [T. A. Davis and W. W. Hager, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606--627]. We also determine how the solution of a linear system Lx = b changes after changing a row and column of C or after a rank-r change in C.
-
Modifying a Sparse Cholesky Factorization
SIAM Journal on Matrix Analysis and Applications, 1999Co-Authors: Timothy A. Davis, William W. HagerAbstract:Given a sparse symmetric positive definite matrix ${\bf AA}^{\sf T}$ and an associated sparse Cholesky Factorization ${\bf LDL}^{\sf T}$ or ${\bf LL}^{\sf T}$, we develop sparse techniques for obtaining the new Factorization associated with either adding a column to ${\bf A}$ or deleting a column from ${\bf A}$. Our techniques are based on an analysis and manipulation of the underlying graph structure and on ideas of Gill et al.\ [ Math. Comp., 28 (1974), pp. 505--535] for modifying a dense Cholesky Factorization. We show that our methods extend to the general case where an arbitrary sparse symmetric positive definite matrix is modified. Our methods are optimal in the sense that they take time proportional to the number of nonzero entries in ${\bf L}$ and ${\bf D}$ that change.