A Fast Direct Solution of Poisson's Equation Using Fourier Analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Fast Direct Solution of Poisson's Equation Using Fourier Analysis

Full text

Pdf (915 KB)

Source

Journal of the ACM (JACM) archive
Volume 12 , Issue 1 (January 1965) table of contents

Pages: 95 - 113

Year of Publication: 1965

ISSN:0004-5411

Author

R. W. Hockney

Computation Center, Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 292, Citation Count: 35

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321250.321259 What is a DOI?

REFERENCES

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	HAGMAN, L. A. Block iterative methods for two cyclic matrix equations. WAPD- TM-327, Westinghouse Bettis Atomic Power Labs., Pittsburgh, Pa., April, 1962.
	2	PRICE, H. S., AND Vagoa, R.S. Recent numerical experiments comparing SOR and ADI methods. Rep. 91, Gulf Research and Development Co., Sept. 1962.
	3	WIHTTAKER AND ROBINSON. Calculus of Observations. Blackie & Son, London, 1944, 260--283.
	4	Milne. Numerical Solution of Differential Equations. Wiley, New York, 10, 225.
	5	PARKAR, S. V. On two-line iterative meLhods for the Laplace and Biharmonic differenee equations. Num. Math. 1,208, 240-252.
	6	JEFHEYS, H., AND JEFFIREYS, B.S. Mathematical Physics. Cambridge U. Press, 1962.
	7	HYMAN, M.A. Non iterative numerical solution of boundary value problems. AppL Sci. Res., B., 2 (1951), 325-351.
	8	LYNCH, R. E., RICE, J. R., AND TIOMAS, D.H. Direct Solution of Partial Differece equations by Tensor Product Methods. Num. Math. 6 (1964), 185q99.
	9	VARCA, R. S. Matrizc Iterative Analysis. Prentice Hall, New York, 11962.
	10	YU, S, P., XOOYgltS, G. P+, BumM., O. Sinufla, tion of distributed-emisim crossed, tield devices. Prec. 5th Internal Cong. Microwave Tubes, Paris, 1964,
	11	BUNEman, O. and WaDHWA R, Solution of Poisson's equation and space ehare neutralisation in ion gun sysVems. Private Communication.
	12	Bickely, W. G, McNts J. Matrix rind other direct methods for the solution of systems of linear difference equtioas. Phil. Tran. Roy. Soc. series A, 52 (1960), 69.

CITED BY 35

	Jung-Gen Wu , Wen-Ming Yan , Kuo-Liang Chung, A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes, Journal of Scientific Computing, v.12 n.4, p.409-431, Dec. 1997
	Richard Reuter, Solving (cyclic) tridiagonal systems, ACM SIGAPL APL Quote Quad, v.18 n.3, p.6-12, March, 1988
	Xian-He Sun, A scalable parallel algorithm for periodic symmetric Toeplitz tridiagonal systems, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	James McCann, Recalling the single-FFT direct Poisson solve, ACM SIGGRAPH 2008 posters, August 11-15, 2008, Los Angeles, California
	D. S. Parker , C. S. Raghavendra, The Gamma network: A multiprocessor interconnection network with redundant paths, ACM SIGARCH Computer Architecture News, v.10 n.3, p.73-80, April 1982
	S. Chandra Sekhara Rao , Sarita, Parallel solution of large symmetric tridiagonal linear systems, Parallel Computing, v.34 n.3, p.177-197, March, 2008
	E. N. Houstis , T. S. Papatheodorou, High-Order Fast Elliptic Equation Solvers, ACM Transactions on Mathematical Software (TOMS), v.5 n.4, p.431-441, Dec. 1979
	Joan-Josep Climent , Leandro Tortosa , Antonio Zamora, A note on the recursive decoupling method for solving tridiagonal linear systems, Applied Mathematics and Computation, v.140 n.1, p.159-164, 30 July 2003
	Harold S. Stone, Parallel Tridiagonal Equation Solvers, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.289-307, Dec. 1975
	J. Verkaik , H. X. Lin, A class of novel parallel algorithms for the solution of tridiagonal systems, Parallel Computing, v.31 n.6, p.563-587, June 2005
	H. X. Lin, Graph transformation and designing parallel sparse matrix algorithms beyond data dependence analysis, Scientific Programming, v.12 n.2, p.91-100, April 2004
	Xian-He Sun , Yu Zhuang, A highly accurate fast solver for Helmholtz equations, Proceedings of the 11th international conference on Supercomputing, p.52-59, July 07-11, 1997, Vienna, Austria
	W. M. Gentleman , G. Sande, Fast Fourier Transforms: for fun and profit, Proceedings of the November 7-10, 1966, fall joint computer conference, November 07-10, 1966, San Francisco, California
	Jef Hendrickx , Marc Van Barel, A Kronecker product variant of the FACR method for solving the generalized Poisson equation, Journal of Computational and Applied Mathematics, v.140 n.1-2, p.369-380, 1 March 2002
	Jules J. Lambiotte, Jr. , Robert G. Voigt, The Solution of Tridiagonal Linear Systems on the CDC STAR 100 Computer, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.308-329, Dec. 1975
	H. A. Presnell , R. P. Pargas, Communication along shortest paths in a tree machine, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.107-114, October 18-22, 1981, Portsmouth, New Hampshire, United States
	R. Colony , R. R. Reynolds, An application of Hockney's method for solving Poisson's equation, Proceedings of the May 5-7, 1970, spring joint computer conference, May 05-07, 1970, Atlantic City, New Jersey
	Xian-He Sun , Wu Zhang, A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.97-106, February 2004
	Holger Bischof , Sergei Gorlatch, A cost-optimal parallel implementation of a tridiagonal system solver using skeletons, Future Generation Computer Systems, v.21 n.5, p.737-742, May 2005
	L. W. Ehrlich, Solving the biharmonic equation in a square: a direct versus a semidirect method, Communications of the ACM, v.16 n.11, p.711-714, Nov. 1973
	Xian-He Sun , Hong Zhang Sun , Lionel M. Ni, Parallel algorithms for solution of tridiagonal systems on multicomputers, Proceedings of the 3rd international conference on Supercomputing, p.303-312, June 05-09, 1989, Crete, Greece
	Victor Y. Pan , Isdor Sobze , Antoine Atinkpahoun, Optimum parallel computations with banded matrices, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.649-658, January 23-25, 1994, Arlington, Virginia, United States
	Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 conference on Supercomputing, p.666-675, October 1990, New York, New York, United States
	Josep-L. Larriba-Pey , Juan J. Navarro , Oriol Roig , Angel Jorba, A generalized vision of some parallel bidiagonal systems solvers, Proceedings of the 8th international conference on Supercomputing, p.404-411, July 11-15, 1994, Manchester, England
	Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.666-675, November 12-16, 1990, New York, New York
	Ilan Bar-on, A practical parallel algorithm for solving band symmetric positive definite systems of linear equations, ACM Transactions on Mathematical Software (TOMS), v.13 n.4, p.323-332, Dec. 1987
	John R. Rice, Algorithmic progress in solving partial differential equations, ACM SIGNUM Newsletter, v.11 n.4, p.6-10, December 1976
	Xian-He Sun , Hong Zhang , Lionel M. Ni, Efficient Tridiagonal Solvers on Multicomputers, IEEE Transactions on Computers, v.41 n.3, p.286-296, March 1992
	Christopher R. Anderson , Thomas C. Cecil, A Fourier-Wachspress method for solving Helmholtz's equation in three-dimensional layered domains, Journal of Computational Physics, v.205 n.2, p.706-718, 20 May 2005
	C.-W. Ho , R. C. T. Lee, A Parallel Algorithm for Solving Sparse Triangular Systems, IEEE Transactions on Computers, v.39 n.6, p.848-852, June 1990
	J. Haslinger , T. Kozubek , K. Kunisch , G. Peichl, Shape Optimization and Fictitious Domain Approach for Solving Free Boundary Problems of Bernoulli Type, Computational Optimization and Applications, v.26 n.3, p.231-251, December 2003
	Anita Mayo , Anne Greenbaum, Fourth order accurate evaluation of integrals in potential theory on exterior 3D regions, Journal of Computational Physics, v.220 n.2, p.900-914, January, 2007
	Jef Hendrickx , Raf Vandebril , Marc Van Barel, A fast direct method for solving the two-dimensional Helmholtz equation, with Robbins boundary conditions, Contemporary mathematics: theory and applications, American Mathematical Society, Boston, MA, 2001
	Benjamin Long , Erik Reinhard, Real-time fluid simulation using discrete sine/cosine transforms, Proceedings of the 2009 symposium on Interactive 3D graphics and games, February 27-March 01, 2009, Boston, Massachusetts
	Y. Charlie Hu , Guohua Jin , S. Lennart Johnsson , Dimitris Kehagias , Nadia Shalaby, HPFBench: a high performance Fortran benchmark suite, ACM Transactions on Mathematical Software (TOMS), v.26 n.1, p.99-149, March 2000