Recently, [1] presented an algorithm for rational matrix multiplication, in which the number of operators needed for carrying out the product of n×m and m×l rational matrices is 0(m(n+l)). The authors of [1]...Recently, [1] presented an algorithm for rational matrix multiplication, in which the number of operators needed for carrying out the product of n×m and m×l rational matrices is 0(m(n+l)). The authors of [1] claimed that their algorithm, at least theoretically, is optimal. In this report, we show that the conclusion of [1] is not true since the computational complexity of an operation depends on the word length of operands. If one accepts the view point of [1], then by inserting zeros and cutting digits, we can present an even 'efficient' algorithm for matrix multiplication, which only needs one multiplication展开更多
文摘Recently, [1] presented an algorithm for rational matrix multiplication, in which the number of operators needed for carrying out the product of n×m and m×l rational matrices is 0(m(n+l)). The authors of [1] claimed that their algorithm, at least theoretically, is optimal. In this report, we show that the conclusion of [1] is not true since the computational complexity of an operation depends on the word length of operands. If one accepts the view point of [1], then by inserting zeros and cutting digits, we can present an even 'efficient' algorithm for matrix multiplication, which only needs one multiplication
