关键词：算法模型；代数结构；算数运算；
摘 要：In 1965 Klyuev and Kokovkin-Shcherbak proved that that n^3/3n3+O(n^2)multiplications are necessary to solve an n-by-n system of linear equations. In 1969 Strassen proved O(n^(log2 7)) multiplications are sucient. They could both be right because they considered di erent models of permitted algorithms. Here we propose yet another algorithmic model, closer in spirit to Klyuev and Kokovkin-Shcherbak, but suciently more general to be able to provide lower bounds on the number of arithmetic operations required to perform dense, sparse or \structured" one-sided matrix factorizations: The simplest (and overly restrictive) version of our assumption is that each scalar result is computed using only the data on which it depends mathematically. We compare these lower bounds with a variety of algorithms and matrix sparsity patterns and algebraic structures (such as Vandermonde). Depending on the sparsity patterns and structures, conventional algorithms may or may not attain the lower bounds. In some cases when they do not, we present new algorithms that do. These bounds are based on a simple, general lower bound for the arithmetic complexity of computing rational functions.