节点导纳矩阵是一个稀疏矩阵，短路电流计算需要对导纳矩阵数据进行查询。为了既能保持快速按行列查询元素数值，又进一步提高按数值查询其所在行列的效率，以便于存储调用及后续矩阵的处理，提出构建高度平衡二叉树的改进十字链表方法，即在十字链表存储的基础上，拓展存储数据结点指针域，形成平衡二叉树，将高度维持在(O(log2 n))，平均查找长度也可维持在(O(log2 n))，大大降低操作时间复杂度，提高数值查询效率。同时，为保证测试结果的公平性，把构建高度平衡二叉树的时间计入总时间，以进行对比。通过相应算例，验证了该改进方法的高效性。

The node admittance matrix is a sparse matrix, and the short circuit current calculation needs to query the admittance matrix data. In order to keep querying the element numerical value according to row and column and to further improve the efficiency of querying the line number according to the numerical value, which can facilitate the storage and subsequent matrix processing, we propose an improved orthogonal list method for constructing the highly balanced binary tree. Based on productive capacity table stores,  the data node pointer field is expanded so as to form a balanced binary tree. The tree’s whose height is maintained at (O(log2 n)),and its average search length is maintained at (O(log2 n)).It can reduce operation time complexity and improve the efficiency of numerical query. At the same time, in order to ensure the fairness of the test results, the time to construct the highly balanced binary tree is included in the total time for comparison. The corresponding examples verify the efficiency of the improved method.
相关文章

[1]	张宗茂, 董德尊, 王子聪, 常俊胜, 张晓云, 王绍聪. 基于便笺式存储器的向量化SpMV算法的性能评估与分析[J]. 计算机工程与科学, 2024, 46(09): 1521-1528.
[2]	周智, 高建花, 计卫星. 基于FPGA和行折叠的稀疏矩阵向量乘优化[J]. 计算机工程与科学, 2024, 46(08): 1340-1348.
[3]	姜晶菲, 何源宏, 许金伟, 许诗瑶, 钱希福. NM-SpMM：面向国产异构向量处理器的半结构化稀疏矩阵乘算法[J]. 计算机工程与科学, 2024, 46(07): 1141-1150.
[4]	施禹, 董攀, 张利军. 一种不规则稀疏矩阵的SpMV方法[J]. 计算机工程与科学, 2024, 46(07): 1175-1184.
[5]	王鑫, 彭健. 基于HYB格式SpMV在新一代申威架构上的实现与优化[J]. 计算机工程与科学, 2023, 45(10): 1754-1762.
[6]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[7]	顾越, 赵银亮. 基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化[J]. 计算机工程与科学, 2022, 44(01): 1-8.
[8]	邹佩钢1,2，陈军1. 基于CombBLAS的同辈压力图聚类并行算法的设计与实现[J]. 计算机工程与科学, 2017, 39(03): 424-429.
[9]	苏锦柱，邬贵明，贾迅. 二元域大型稀疏矩阵向量乘的FPGA设计与实现[J]. 计算机工程与科学, 2016, 38(08): 1530-1535.
[10]	阳王东1,2 ,李肯立2. 基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化[J]. J4, 2016, 38(02): 202-209.
[11]	许彬彬，戴清平，朱敏，谢端强. 基于哈夫曼编码的稀疏矩阵的存储与计算[J]. J4, 2013, 35(11): 134-138.
[12]	邓林，窦勇，郑义. 面向稀疏矩阵访存特性的Cache划分[J]. J4, 2012, 34(9): 64-70.
[13]	秦晋，龚春叶，胡庆丰，刘杰. 基于CUDA编程模型的稀疏对角矩阵向量乘优化[J]. J4, 2012, 34(7): 78-83.
[14]	刘杰 迟利华 胡庆丰 李晓梅. 并行计算稀疏矩阵乘以向量的负载平衡算法[J]. J4, 2006, 28(3): 76-77.
[15]	戴春来. 对基于稀疏矩阵分解求解约束系统方法的改进[J]. J4, 2004, 26(9): 52-53.