LDL-factorization is an efficient way of solving Ax = b for a large symmetric positive definite sparse matrix A. This paper presents a new method that further improves the efficiency of LDL-factorization. It is based ...LDL-factorization is an efficient way of solving Ax = b for a large symmetric positive definite sparse matrix A. This paper presents a new method that further improves the efficiency of LDL-factorization. It is based on the theory of elimination trees for the factorization factor. It breaks the computations involved in LDL-factorization down into two stages： 1） the pattern of nonzero entries of the factor is predicted, and 2） the numerical values of the nonzero entries of the factor are computed. The factor is stored using the form of an elimination tree so as to reduce memory usage and avoid unnecessary numerical operations. The calculation results for some typical numerical examples demonstrate that this method provides a significantly higher calculation efficiency for the one-to-one marketing optimization algorithm.展开更多
Electrical power network analysis and computation play an important role in the planning and operation of the power grid,and they are modeled mathematically as differential equations and network algebraic equations.Th...Electrical power network analysis and computation play an important role in the planning and operation of the power grid,and they are modeled mathematically as differential equations and network algebraic equations.The direct method based on Gaussian elimination theory can obtain analytical results.Two factors affect computing efficiency:the number of nonzero element fillings and the length of elimination tree.This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories.The Approximate Minimum Degree(AMD)of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length(AMDML)model.The quotient graph node with the minimum degree,which is also the minimum length of elimination tree node,is selected as the next ordering vector.Compared with AMD ordering method and other common methods,the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings;the length was decreased by about 10%compared with the AMD method.A testbed for experiment was built.The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.展开更多
基金This work was supported in part by the National Natural Science Foundation of PRC (No.60425310)the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE,PRC.
文摘LDL-factorization is an efficient way of solving Ax = b for a large symmetric positive definite sparse matrix A. This paper presents a new method that further improves the efficiency of LDL-factorization. It is based on the theory of elimination trees for the factorization factor. It breaks the computations involved in LDL-factorization down into two stages： 1） the pattern of nonzero entries of the factor is predicted, and 2） the numerical values of the nonzero entries of the factor are computed. The factor is stored using the form of an elimination tree so as to reduce memory usage and avoid unnecessary numerical operations. The calculation results for some typical numerical examples demonstrate that this method provides a significantly higher calculation efficiency for the one-to-one marketing optimization algorithm.
基金supported in part by the National Key Basic Research and Development Program of China(No.2017YFE0132100)the Tsinghua-Toyota Research Fund(No.20203910016)the BNRist Program(No.BNR2020TD01009)。
文摘Electrical power network analysis and computation play an important role in the planning and operation of the power grid,and they are modeled mathematically as differential equations and network algebraic equations.The direct method based on Gaussian elimination theory can obtain analytical results.Two factors affect computing efficiency:the number of nonzero element fillings and the length of elimination tree.This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories.The Approximate Minimum Degree(AMD)of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length(AMDML)model.The quotient graph node with the minimum degree,which is also the minimum length of elimination tree node,is selected as the next ordering vector.Compared with AMD ordering method and other common methods,the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings;the length was decreased by about 10%compared with the AMD method.A testbed for experiment was built.The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.
