This paper proposes a two-parameter block triangular splitting(TPTS)preconditioner for the general block two-by-two linear systems.The eigenvalues of the corresponding preconditioned matrix are proved to cluster aroun...This paper proposes a two-parameter block triangular splitting(TPTS)preconditioner for the general block two-by-two linear systems.The eigenvalues of the corresponding preconditioned matrix are proved to cluster around 0 or 1 under mild conditions.The limited numerical results show that the TPTS preconditioner is more efficient than the classic block-diagonal and block-triangular preconditioners when applied to the flexible generalized minimal residual(FGMRES)method.展开更多
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
Sparse representation(SR)is a fundamental component of linear representation techniques and plays a crucial role in signal processing,machine learning,and computer vision.Most parallel methods for solving sparse repre...Sparse representation(SR)is a fundamental component of linear representation techniques and plays a crucial role in signal processing,machine learning,and computer vision.Most parallel methods for solving sparse representations rely on the alternating direction method of multipliers(ADMM).However,the classical 2-block ADMM or N-block ADMM often suffer from three problems:(1)solving the subproblem requires solving a linear system,(2)unsuitable sparse data structure for parallelization,and(3)unsatisfactory parallel efficiency and scalability performance.In this paper,we propose a parallel ADMM-based algorithm called block splitting proximal ADMM(BSPADMM).First,BSPADMM organizes the sparse signals in the compressed sparse columns(CSC)format,and each processor deals with them independently.Second,BSPADMM designs the proximal term that avoids solving a linear system of the subproblem during iterations.Its advantage is that the BSPADMM computes the subproblem by using sparse matrix-vector multiplication,without communication between processors.Third,each processor updates the size asynchronously,which eliminates the synchronization effort of adjusting the step size between processes.Thus,the communication overhead can be naturally reduced.Our experimental results on three datasets of varying scales show that BSPADMM outperforms state-of-the-art ADMM techniques,including the adaptive relaxed ADMM(ARADMM)and N-block ADMM,in terms of computing time and parallel efficiency.BSPADMM runs 1.64 times faster than the N-block ADMM,and the ratio grows to 8.27 times as the dataset size doubles.More importantly,the parallel efficiency of BSPADMM remains above 70%as the number of processors grows to 10,000,demonstrating strong scalability.展开更多
基金the National Natural Science Foundation of China under Grant Nos.61273311 and 61803247.
文摘This paper proposes a two-parameter block triangular splitting(TPTS)preconditioner for the general block two-by-two linear systems.The eigenvalues of the corresponding preconditioned matrix are proved to cluster around 0 or 1 under mild conditions.The limited numerical results show that the TPTS preconditioner is more efficient than the classic block-diagonal and block-triangular preconditioners when applied to the flexible generalized minimal residual(FGMRES)method.
文摘Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
基金supported by the National Science Foundationhttp://dx.doi.org/10.13039/100000001 under Grant No.nnnnnnn and Grant No.mmmmmmm.
文摘Sparse representation(SR)is a fundamental component of linear representation techniques and plays a crucial role in signal processing,machine learning,and computer vision.Most parallel methods for solving sparse representations rely on the alternating direction method of multipliers(ADMM).However,the classical 2-block ADMM or N-block ADMM often suffer from three problems:(1)solving the subproblem requires solving a linear system,(2)unsuitable sparse data structure for parallelization,and(3)unsatisfactory parallel efficiency and scalability performance.In this paper,we propose a parallel ADMM-based algorithm called block splitting proximal ADMM(BSPADMM).First,BSPADMM organizes the sparse signals in the compressed sparse columns(CSC)format,and each processor deals with them independently.Second,BSPADMM designs the proximal term that avoids solving a linear system of the subproblem during iterations.Its advantage is that the BSPADMM computes the subproblem by using sparse matrix-vector multiplication,without communication between processors.Third,each processor updates the size asynchronously,which eliminates the synchronization effort of adjusting the step size between processes.Thus,the communication overhead can be naturally reduced.Our experimental results on three datasets of varying scales show that BSPADMM outperforms state-of-the-art ADMM techniques,including the adaptive relaxed ADMM(ARADMM)and N-block ADMM,in terms of computing time and parallel efficiency.BSPADMM runs 1.64 times faster than the N-block ADMM,and the ratio grows to 8.27 times as the dataset size doubles.More importantly,the parallel efficiency of BSPADMM remains above 70%as the number of processors grows to 10,000,demonstrating strong scalability.
