Asymptotically fast solution of Toeplitz-like singular linear systems

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bitmead~ It. R. and Anderson~ B. D. O., "Asymtotically fast solution of Toeplitz and related systems of linear equations," Linear Algebra Applic. 34, pp. 103-116 (1980).
	2	Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).
	3	John F. Canny , Ioannis Z. Emiris, An Efficient Algorithm for the Sparse Mixed Resultant, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.89-104, May 10-14, 1993
	4	Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
	5	Delsarte, P., Genin~ Y. V., and Kamp, Y. G., "A generMization of the Levinson algorithm for ttermitian Toeplitz matrices with any rank profile," IEEE Trans. Acoustics, Speech, and Signal Process. ASSP-33/4, (19s5).
	6	DeMillo, 1~. A. and Lipton, 1%. J., "A probabilistic remark on algebraic program testing," Information Process. Letters 7/4, pp. 193-195 (1978).
	7	Angel Díaz , Markus A. Hitz , Erich Kaltofen , A. Lobo , T. Valente, Process Scheduling in DSC and the Large Sparse Linear Systems Challenge, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.66-80, September 15-17, 1993
	8	Feng, G. L., Wei, V. K., l~ao, T. 1%. N., and Tzeng, K. K., "True designed-distance decoding of a class of algebraic-geometric codes, Part II: fast algorithms and Toeplitz-block Toeplitz matrices," IEEE Trans. Inf Theory, ~o appear (1994).
	9	Gohberg, i., Kailath, T., and Koltracht, I., "Efficient solution of linear systems of equations with recursire structure," Linear Algebra Appiic. 80, pp. 81- 113 (1986).
	10	Gohberg, I. C. and Semencul, A. A., "On the inversion of finite Toeplitz matrices and their continous analogues," Mat. Issled. 2, pp. 201-233 (1972). In Russian. Math. Rev. MR 50~5524.
	11	Hong, H., "Quantifier elimination for formulas constrained by quadratic equations via slope resultants," The Computer J. 36/5, pp. 439-449 (1993).
	12	Kailath, T., Kung, S.-Y., and Morf, M., "Displacement ranks of matrices and linear equations," J. Math. Analysis Applications 68, pp. 395-407 (1979).
	13	M. Kalkbrener , M. Sweedler , L. Taylor, Low degree solutions to linear equations with K[x] coefficients, Journal of Symbolic Computation, v.16 n.1, p.75-81, July 1993 [doi>10.1006/jsco.1993.1034]
	14	Kaltofen, E., "Etficient Solution of Sparse Linear Systems," Lect. Notes, Dept. Comput. Sci., Itensselaer Polytech. Inst., Troy, New York, 1992. Available from anonymous@ftp, cs .rpi. edu in directory kaltofen.
	15	Erich Kaltofen, Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.195-212, May 10-14, 1993
	16	Erich Kaltofen, Direct proof of a theorem by Kalkbrener, Sweedler, and Taylor, ACM SIGSAM Bulletin, v.27 n.4, p.2, Dec. 1993 [doi>10.1145/182125.182126]
	17	Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
	18	Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
	19	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
	20	Morf, M., "Doubling algorithms for Toeplitz and related equations," in Proc. 1980 IEEE In ternat. Conf. Acoust. Speech SignM Process.; IEEE, pp. 954-959, 1980.
	21	Pan, V., "Parameterization of Newton's iteration for computations with structured matrices and applications," Computers Math. Applic. 24/3, pp. 61-75 (1992).
	22	Sasaki, T. and Furukawa, A., "Secondary polynomial remainder sequence and an extension of the subresultant theory," J. Inform. Process 7/;I, pp. 176-184 (1984).
	23	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	24	Strassen, V., "The computational complexity of continued fractions," SIAM J. Comput. 12/1, pp. 1-27 (1983).
	25	Trench, W., "An algorithm for the inversion of finite Toeplitz matrices," SIAM J. Appl. Math. 12, pp. 515- 522 (1964).
	26	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	27	Zippel, It., Effective Polynomial Computations; Kluwer Academic Publ., Boston, Massachusetts, 1993; 384pp.