| The solution of linear equations is widely used in engineering,computer science,physics,mathematics,economics,statistics,mechanics,signal processing,communication,aviation and other disciplines and fields.The coefficient matrix A of linear equations that need to be solved in science and technology and engineering problems is usually large or giant sparse symmetric positive definite matrix.Cholesky decomposition is used to decompose the coefficient matrix A into the product of two triangular matrices,which can transform the original complex solving problem of linear equations into simple solving problem of trigonometry.It is usually an efficient algorithm for solving large linear equations,also known as sparse direct method.Sparse direct methods are used to solve linear algebra problems,including linear equations,sparse linear squares and eigenvalue problems,and form the backbone of many applications in computational science.Although the computing speed,memory and external storage capacity of the computer are constantly improving,but with the increase of complexity of practical engineering problems and the continuous improvement of analysis requirements,the improvement of computer performance can not fully meet the requirements of large-scale computing.Therefore,it is necessary to study how to save storage and improve computational efficiency of sparse Cholesky decomposition algorithm.Supernodal method is a high performance direct method for solving large sparse linear systems.Compared with the traditional algorithms,the supernodal method has the advantage of generating dense submatrices in the decomposition process,thus transforming the sparse matrix operation into dense matrix operation,making full use of the performance of dense matrix kernel,transforming irregular memory access into regular memory access,and greatly improving the computing performance.Supernode structure is the key of supernodal method.If the relaxed supernode is too small,it will reduce the granularity of parallel computing,while if the relaxed supernode is too large,it will bring too much storage and computing overhead.Therefore,the relaxation parameters of control node merging should be set within a reasonable range.The traditional relaxation parameters are usually set empirically and only have certain effects on some specific matrices.This paper presents an adaptive algorithm for selecting optimal relaxation parameters based on neural network.The algorithm redefines the relaxation parameters and makes them suitable for neural network modeling.This method is characterized by the size of the matrix,the number of non-zero elements,sparseness,Flops/Lnz,and the main parameters of the basic super-node elimination tree,and labels the corresponding relaxation parameter with the shortest computation time to build a 5-classification model.The model has wide adaptability and the accuracy of optimal relaxation parameter calculation is more than80%.Compared with Cholmod algorithm,the decomposition performance of adaptive tuning algorithm is improved by 4.5～33%.A sparse Cholesky parallel numerical decomposition algorithm is also proposed in this paper.By analyzing the calculation process of each supernode,the algorithm explores the data dependence relationship in the decomposition step,and divides the supernode into two types.One is the supernode of the same layer,whose decomposition step has no dependence and can be carried out in parallel computing,but there may be conflicts in data update of the supernode of the same layer with a common parent node.The other is parent-child nodes with dependencies.The parallel algorithm proposed in this paper is based on the supernode elimination tree structure,in which each relaxed supernode of the elimination tree is simultaneously mapped to the computing core of each processor as an independent computing task.In this paper,the algorithm is proposed to decompose and eliminate the nodes of the tree layer by layer in a bottom-up manner,which provides the strategy of hierarchical parallel task division among the supernodes,and uses the low-level parallel matrix multiplication inside the supernodes to realize the parallel computation with the combination of coarse and fine granularity.At the same time,we introduce a thread pool mechanism to avoid the cost of creating and destroying threads when dealing with short time tasks,and improve the parallel performance.Experimental results on kunpeng 920 processor show that the acceleration ratio of the proposed parallel algorithm can reach 1.5～5.5,and the multi-core performance can reach 1.2～2.8 times that of Cholmod algorithm. |
