NDLI: A parallel fast Fourier transform on multipoles (FFTM) algorithm for electrostatics analysis of three-dimensional structures

Content Provider	IEEE Xplore Digital Library
Author	Eng Teo Ong Heow Pueh Lee Kian Meng Lim
Copyright Year	1982
Abstract	A fast algorithm, called the fast Fourier transform on multipoles (FFTM) method, is developed for efficient solution of the integral equation in the boundary element method (BEM). This method employs the multipole and local expansions to approximate far field potentials, and uses the fast Fourier transform (FFT) to accelerate the multipole to local translation operator based on its convolution nature. The series of uncoupled convolutions allows further speed up in the algorithm through parallel computation. In this paper, we present the results of using the FFTM algorithm for solving large-scale three-dimensional electrostatic problems. It is demonstrated that the method can give accurate results with relatively low order of expansion. It is also found that the serial version of the algorithm has computational complexities of O(N/sup a/), where a ranges from 1.0 to 1.4 for computational time, and from 1.1 to 1.2 for memory storage requirement. Significant speedup is also observed in the parallel implementation of FFTM using up to 16 processors on an IBM-p690 supercomputer.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1063
Ending Page	1072
Page Count	10
File Size	574196
File Format	PDF
ISSN	02780070
Volume Number	23
Issue Number	7
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-07-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Fast Fourier transforms Electrostatic analysis Convolution Integral equations Boundary element methods Acceleration Concurrent computing Large-scale systems Computational complexity Supercomputers
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Accelerating the Nonequispaced Fast Fourier Transform on Commodity Graphics Hardware

Fast BEM Solvers for 3D Poisson-Type Equations

2D Discrete Fourier Transform on Sliding Windows

A Parallel Implementation of the Fast Fourier Transform Algorithm

Parallel and Pipelined Architectures for Cyclic Convolution by Block Circulant Formulation Using Low-Complexity Short-Length Algorithms

Fast Fourier transform on multipoles (FFTM) algorithm for Laplace equation with direct and indirect boundary element method

Fast Parallel Approach for 2-D DHT-Based Real-Valued Discrete Gabor Transform

Supercomputers and Graphics

Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform

A parallel fast Fourier transform on multipoles (FFTM) algorithm for electrostatics analysis of three-dimensional structures

Similar Documents

Accelerating the Nonequispaced Fast Fourier Transform on Commodity Graphics Hardware

Fast BEM Solvers for 3D Poisson-Type Equations

2D Discrete Fourier Transform on Sliding Windows

A Parallel Implementation of the Fast Fourier Transform Algorithm

Parallel and Pipelined Architectures for Cyclic Convolution by Block Circulant Formulation Using Low-Complexity Short-Length Algorithms

Fast Fourier transform on multipoles (FFTM) algorithm for Laplace equation with direct and indirect boundary element method

Fast Parallel Approach for 2-D DHT-Based Real-Valued Discrete Gabor Transform

Supercomputers and Graphics

Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform

A parallel fast Fourier transform on multipoles (FFTM) algorithm for electrostatics analysis of three-dimensional structures