An efficient algorithm for chain multiplication of dense matrices and its computer implementation - Details

author：

Zhu, Daxin (Zhu, Daxin.) ^[1] | Wu, Yingjie (Wu, Yingjie.) ^[2] | Wang, Xiaodong (Wang, Xiaodong.) ^[3]

Indexed by：

EI Scopus

Abstract：

In　this　work,　we　consider　the　matrix　chain　ordering　problem　to　determine　the　optimal　computation　order　of　the　matrix　chain　products.　A　new　algorithm　for　the　matrix　chain　ordering　problem　is　presented.　The　time　complexity　of　the　presented　algorithm　is　O(n　logm),　where　n　is　the　number　of　matrices　in　the　chain　and　m　is　the　number　of　local　minimums　in　the　dimension　sequence　of　the　given　matrix　chain.　When　m　is　a　fixed　constant,　the　new　algorithm　requires　only　O(n)　time.　The　new　algorithm　is　not　only　an　improvement　on　the　time　complexity　compared　to　the　O(n　log　n)　time　algorithm　of　Hu　and　Shing,　but　also　substantially　simpler　than　the　Hu-Shing　algorithm.　1553-9105/Copyright　©　2014　Binary　Information　Press.

Keyword：

Algorithms Chains Computational complexity Dynamic programming

Community：

[ 1 ] [Zhu, Daxin]Faculty of Mathematics and Computer Science, Quanzhou Normal University, Quanzhou 362000, China
[ 2 ] [Wu, Yingjie]Faculty of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
[ 3 ] [Wang, Xiaodong]Faculty of Mathematics and Computer Science, Quanzhou Normal University, Quanzhou 362000, China
[ 4 ] [Wang, Xiaodong]Faculty of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China