Continuous Functions with a Dense Set of Proper Local Maxima
Vladimir Drobot, Michał Morayne · American Mathematical Monthly · 1985
for the number of multiplications to get D in triangular form. There will then be n multiplications (of diagonal entries) to compute det(D), requiring 0(n4) multiplications. As before, we do not consider the more sophisticated algorithms for computing determinants. We remark that there is an algorithm of V. Strassen that uses divide-and-conquer to reduce the number of multiplications but with a similar order of magnitude. A similar situation holds for the computation of each of the (n 1)-minors of D. Since there are n 1 such minors, the multiplicative complexity is (n 1)0(n4) = 0(n5) with constant no more than 1/3. We compute the gcd of the polynomial which are the (n 1)-minors of D using the Eucidean algorithm on the first two, then on their gcd and the third, etc. An upper bound for the number of multiplication/division steps when dividing two polynomials of degree n 1 is n divisions and 0(n2) multiplications. Since there are n 1 polynomials, there are 0(n4) such computations. Thus the classical method requires