Исторические замечания и литература

1. Браун в обеих своих статьях (1971, р. 485, 1978, р. 238) и Кнут (1981, р. 410) приписывают Коллинзу (1967) открытие метода Сильвестра-Габихта субрезультантных PRS. Как мы показали, это открытие было начато Сильвестром в 1853 г. и завершено Габихтом в 1948 г. В этой книге впервые должное было отдано

тому, кому оно принадлежит. [См. также в этом контексте (Fryer, 1959).]

2. Статьи Сильвестра (1853) и Ван Влека (1899) не упоминаются в обзорной статье Лооса (1982).

3. Мы отдаем должное Доджсону (Dodgson, 1866), а не Барейсу (Bareiss, 1968) за сохраняющие целочисленность преобразования. См. также работу (Waugh, Dwyer, 1945), в которой используется тот же метод, что и у Барейса, но на 23 года раньше. Авторы последней работы указывают на Доджсона как на своего предшественника; их подход отличается только тем, что они не используют подвижный ведущий элемент (Waugh, Dwyer, 1945, p. 266). Доджсон — это человек, известный главным образом своими литературными произведениями под псевдонимом Льюис Кэрролл.

4. Дальнейшее исследование и развитие метода матричной триангуляризации субрезультантных PRS см. в работе (Akritas, Akritas, Malaschonok, 1992). Получены теоретические результаты, не зависящие от теоремы Ван Влека (которая не всегда верна), где вместо преобразования матрицы порядка преобразуется матрица порядка m + n.

Малашонок Г.И. Решение системы линейных уравнений над областью целостности. Журнал вычислительной математики и математической физики 23, 1497-1500, 1983.

Малашонок Г. И. Система линейных уравнений над коммутативным кольцом. — Львов: ФМИ АН УССР, 1986 (препринт № 114).

Akritas A.G. A new method for computing polynomial greatest common divisors. University of Kansas, TR-86-9, Lawrence, Kansas, 1986.

Akritas A.G. A simple proof of the validity of the reduced prs algorithm. Computing 38, 369-372, 1987.

Akritas A.G. A new subresultant prs method. Proceedings ot the 12th IMACS World Congress on Scientific Computation (July 1988, Paris, France), 4, 654-655, 1988.

Akritas A.G. A new method for computing polynomial greatest common divisors and polynomial remainder sequences. Numerische Mathe-matik, 52, 119-127, 1988.

Akritas A.G., Akritas E.K., Malaschonok G.I. Computation of polynomial remainder sequences in integral domains. Submitted for publication, 1992.

Anderson G. An examination of polynomial remainder sequences. M.S. Thesis, University of Kansas, Department of Computer Science, Lawrence, KS, 1986.

Bareiss E.H. Sylvester’s identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation 22, 565-578, 1968.

Barnett S. Polynomials and Linear Control Systems. Marcel Dekker Inc., New York & Basel, 1983.

Barnett S. A new look at classical algorithms for polynomial resultant and gcd calculation. SIAM Review 16, 193-206, 1974.

Berlekamp E.R. Algebraic coding theory. McGraw-Hill, New York, 1968. [Имеется перевод: Берлекэмп Э. Алгебраическая теория кодирования. — М.: Мир, 1974.]

Bocher М. Introduction to higher algebra. MacMillan, New York, 1907.

Brown W.S. On Euclid’s algorithm and the computation of polynomial greatest common divisors. Journal of Association for Computing Machinery 18, 476-504, 1971.

Brown W.S. The subresultant prs algorithm. ACM Transactions on Mathematical Software 4, 237-249, 1978.

Brown W.S., Traub J.F. On Euclid’s algorithm and the theory of subresultants. Journal of Association for Computing Machinery 18, 505-514, 1971,

Collins G.E. Polynomial remainder sequences and determinants. American Mathematical Monthly 73, 708-712, 1966.

Collins G.E. Subresultants and reduced polynomial remainder sequences. Journal of Association for Computing Machinery 14, 128-142, 1967.

Collins G.E. The calculation of multivariate polynomial resultants. Journal of Association for Computing Machinery 19, 515-532, 1971.

Dodgson C.L. Condensation of determinants. Proceedings of the Royal Society of London 15, 150-155, 1866.

Fryer W.D. Applications of Routh’s algorithm to network theory problems. IEEE Transactions on Circuit Theory CT-6, 144-149, 1959.

Gonzalez L., Lombardi H., Recio Т., Roy M.-F. Specialization de la suite de Sturm et sous-resultants. Preprint Num. 8-1990, Department of Mathematics Statistics and Computation, University of Cantabria, 39071 Santander, Spain.

Habicht W. Eine Verallgemeinerung des Sturmschen Wurzelzaehlver-fahrens. Commentarii Mathematici ffelvetici 21, 99-116, 1948.

Householder A.S. The numerical treatment of a single nonlinear equation. McGraw-Hill, New York, 1970.

Knuth D.E. The art of computer programming. Vol. 2, 2nd ed. Seminu-merical Algorithms. Addison-Wesley, Reading, MA 1981. [Имеется перевод первого издания: Кнут Д. Искусство программирования для ЭВМ. Т. 2. — М.: Мир, 1977.]

Laidacker М.А. Another theorem relating Sylvester’s matrix and the greatest common divisor. Mathematics Magazine 42, 126-128, 1969.

Lipson J.D. Elements of algebra and algebraic computing. Addison-Wesley. Reading, MA, 1981.

Loos R. Generalized polynomial remainder sequences. In Computer Algebra Symbolic and Algebraic Computations. B. Buchberger, G.E. Collins, and R. Loos eds. Springer Verlag, New York, 1982, Computing Supplement 4, 115-137. [Имеется перевод: JIooc P. Обобщенные последовательности полиномиальных остатков. — В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. — М.: Мир, 1986, с. 151-171.]

Miola A., Yun D.Y.Y. Computational aspects of Hensel-type univariate polynomial greatest common divisor algorithms. Proceedings of EUROSAM 1974, PP- 46-54 (also ACM SIGSAM Bulletin SI).

Moses J., Yun D.Y.Y. The EZGCD algorithm. Proceedings of the ACM Annual Conference (August 1973, Atlanta), pp. 159-166.

Muir T. A treatise on the theory of determinants. Macmillan, London, 1882.

Muir T. The theory of determinants. Vol III. Macmillan, London, 1920.

Netto E. Voriesungen ueber Algebra. Erster Band. Teubner, Leipzig, 1896.

Sylvester J.J. On a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm’s functions, and that of the greatest algebraical common measure. Philosophical Transactions 143, 407-548, 1853.

Van Vleck, E. B. On the determination of a series of Sturm’s functions by the calculation of a single determinant. Annals of Mathematics, Second Series 1, 1-13, 1899-1900.

Waugh F.V., Dwyer P.S. Compact computation of the inverse of a matrix. Annals of Mathematical Statistics 16, 259-271, 1945.

Yun D.Y.Y. The Hensel lemma in algebraic manipulation. Ph.D. Thesis, Department of Mathematics, MIT, 1974.