Papers by Reif on Sequential and Parallel Algebraic
and Numerical Algorithms (28 papers)
2.
John H. Reif,
Logarithmic Depth Circuits for Algebraic Functions. 24th Annual IEEE Symposium on Foundations of Computer Science,
Tucson, AZ, November 1983, pp. 138-145. Published in SIAM Journal on Computing, Vol.
15, No. 1, February 1986, pp. 231-242. [PDF]
3.
John H. Reif,
Probabilistic Parallel Prefix Computation, 13th
Annual International Conference on Parallel Processing, Michigan, 1984. Published in Computers
and Mathematics with Applications, Vol. 26, Number 1, July 1993, pp.
101-110. [PDF]
6.
Victor Y. Pan
and John H. Reif, Efficient Parallel Solution of Linear Systems. 17th Annual ACM Symposium on Theory of
Computing(STOC 85), Providence, RI, May 1985, pp. 143-(ACM Press, New York) 152.
Presented at the meeting on Efficient Algorithms, Mathematisches
Forschungsinstitut, Oberwolfach, W. Germany, November 1984. Presented at 2nd SIAM Conference on Applied Linear
Algebra, Raleigh, NC, April 1985. Published as Fast and Efficient Parallel
Solution of Sparse Linear Systems. SIAM
Journal on Computing, Vol. 22, No. 6, pp. 1227-1250, December 1993. [PDF]
or [PDF]
7.
Victor Y. Pan
and John H. Reif, Fast and Efficient Algorithms for Linear Programming and for
the Linear Least Squares Problem, 12th
International Symposium on Mathematical Programming, MIT, Cambridge, MA, pp. 283-295, August 1985. Abstract published
as Efficient Parallel Linear Programming, Operations
Research Letters, Vol. 5, No. 3,
August 1986, pp. 127-135. [PDF] Also presented as Fast and Efficient Parallel
Linear Programming and Least Squares Computations at Aegean Workshop on
Computing, Loutraki, Greece, July 1986; Lecture
Notes in Computer Science, Springer-Verlag, Vol. 227, 1986, pp. 283-295. Full Paper published
as Fast and Efficient Linear Programming and Linear Least-Squares Computations,
Computers and Mathematics with
Applications, Vol. 12A, No. 12,
1986, pp. 1217-1227. [PDF]
8.
Victor Y. Pan
and John H. Reif, Fast and Efficient Parallel Solution of Dense Linear Systems.
Computers and Mathematics with
Applications, Vol. 17, No. 11, 1989, pp. 1481-1491. [PDF]
11.
John H. Reif
and Steve R. Tate, On Threshold Circuits and Polynomial Computation. 2nd Structure in Complexity Theory
Conference, Ithaca, NY, June
1987. Published in SIAM Journal on
Computing, Vol.21, No. 5, October 1992, 896-908. [PDF]
or [PostScript]
[PDF]
12.
Victor Y. Pan
and John H. Reif, Some Polynomial and Toeplitz Matrix Computations. 28th Annual IEEE Symposium on Foundations of
Computer Science, Los Angeles, CA, October 1987, (IEEE
Computer Society Press) pp.
173-184. [PDF]
13.
John H. Reif and
Steve R. Tate, Optimal Size Integer Division Circuits. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May
1989, pp. 264-273. Presented at
meeting on Efficient Algorithms, Mathematisches Forschungsinstitut, W. Germany,
September 1989. Published in SIAM Journal
on Computing, Vol. 19, No. 5, October 1990, pp. 912-924. [PDF]
or [PostScript]
[PDF]
or [PostScript]
18.
J. Cheriyan
and John H. Reif, Parallel and Output Sensitive Algorithms for Combinatorial
and Linear Algebra Problems, 1992. 4th
Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'93),
Velon, Germany, July 1993, p.50-56. Published as John H. Reif, Parallel Output
Sensitive Algorithms for Combinatorial and Linear Algebra Problems, Journal of Computer and System Sciences,
Vol. 62, May 2001, pp. 398-412. [PostScript] [PDF]
19.
John H. Reif,
O(log2 n) Time Efficient Parallel Factorization of Dense, Sparse
Separable, and Banded Matrices. 5th
Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94),
Cape May, NJ, June 1994, pp. 114-121. [PostScript]
[PDF]
20.
John H. Reif,
An O(n log^3 n) Algorithm for
the Real Root Problem. 34th Annual IEEE
Conference on Foundations of Computer Science (FOCS '93) Proceedings,
November 1993, Palo Alto, CA, pp. 626-635. Revised as An Efficient Algorithm
for the Real Root and Symmetric Tridiagonal Eigenvalue Problems, 1994. [PostScript] [PDF] and [PostscriptFigures]
22.
Victor Y. Pan
and John H. Reif, Generalized Compact Multi-grid, Computers Math Applications, Volume 25, Number 9, p.3-5, May 1993.
[PDF]
23.
John H. Reif
and Steve R. Tate, Dynamic Algebraic Algorithms, Proceedings of the 5th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA'94), TX, Jan. 1994.
pp.290-301. Published as On Dynamic Algorithms for Algebraic Problems, Journal
of Algorithms, Volume 22, Number 2, pp. 347-371, February 1997. [PostScript]
[PDF]
24.
John H. Reif,
Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems, Proceedings of the 36th Annual IEEE
Symposium on Foundations of Computer Science (FOCS'95) Milwaukee, WI,
October 23-25, 1995, pp. 123-132. Published as Efficient Parallel Computation
of the Characteristic Polynomial of a Sparse, Separable Matrix, Algorithmica,
29: pp, 487-510 (2001). [PostScript] [PDF]
25.
John H. Reif,
Work Efficient Parallel Solution of Toeplitz Systems and Polynomial GCD. Proc. of the 27th ACM Symposium on Theory of
Computing (STOC 95), Las Vegas, NV, May 29-June 1, 1995, pp. 751-761.
Revised as Efficient Parallel Factorization and Solution of Structured and
Unstructured Linear Systems, Journal of
Computer and System Sciences, Vol. 71,
Issue 1 (July 2005), pp. 86 - 143. [PDF] [PDF]
26.
John H. Reif,
Efficient Approximate Solution of Sparse Linear Systems, Published in Computers and Mathematics with Applications,
Vol. 36, No. 9, Nov. 1998, pp. 37-58. [PostScript] [PDF] (Also, see errata,
Computers and Mathematics with Applications, Vol. 38, No. 9, 1999, pp. 141-141. [PDF])
27.
John H. Reif,
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.
Proc. 29th ACM Symposium on Theory of Computing (STOC97), El Paso, Texas, pp.
30-39 (May 4-6, 1997). Published in SIAM
Journal of Computing (SICOMP), Vol. 28. Number 6,
pp. 2059-2089, 1999. [PostScript] [PDF]
28.
Andrew Neff
and John H. Reif, An O(n^{1+epsilon} log b) Algorithm for the Complex Roots Problem. 35th Annual IEEE Conference on Foundations of Computer Science (FOCS
'94) Proceedings, Santa Fe, NM, November 1994. pp. 540-547. Andrew Neff and
John H. Reif, An O(n^{1+epsilon} logb) Algorithm for the Complex Roots Problem. 35th Annual IEEE Conference on Foundations of Computer Science (FOCS
'94) Proceedings, Santa Fe, NM, November 1994. pp. 540-547. Improved Paper
Published as An Efficient Algorithm for the Complex Roots Problem, Journal of
Complexity, 12(2) pp. 81-115, (June 1996). [PostScript] [PDF]