高階行列式計算問題的分治算法探討

胡能發

【摘 要】設計了一種大規模行列式計算問題的分治算法，該算法首先將原行列式的維度擴充到2或者3的冪維度，然后分割為規模相等的獨立子問題分別求解。該算法所分解的各獨立模塊可以并行執行，因此，對于高維度行列式的計算，提供了一種參考途徑。

【關鍵詞】高階行列式;分治算法;復雜度

中圖分類號： O151.2-4;G642 文獻標識碼： A 文章編號： 2095-2457（2019）01-0156-002

0 引言

在數學及其它許多學科中，常常要計算行列式，如工程中電路設計的符號分析、線性系統的求解、結式計算及雅可比行列式計算等等。

在行列式的計算方面已有許多行之有效的方法，其中比較常見的方法是降階計算、例用插值計算等等。但當行列式的階較大時，其計算量也較大。因此本文提出了一種計算行列式的新方法，該方法采用分治算法的思想，結合并行計算，從而較大地提高了計算速度。

由上可知，無論采用怎樣的分割方法，算法都會以線性時間求解。由于各子問題是相互獨立的，因此，在計算時可以并行計算，從而可以大大地提高計算速度。

【參考文獻】

[1]王曉東.算法設計與分析[M].北京：汪華大學出版社，2005.

[2]劉洋，唐好選.針對路面建模的Delaunay三角網格分治算法[J].智能計算機與應用，2017，7（2）：87-89.

[3]杜青.基于類的大整數乘法運算的實現[J].微型機與應用，2017，36（2）：8-9.