Orderings and partition of PDE computations for a fixed-size VLSI architecture
Pages 366 - 375
Abstract
The parallel iterative solution of systems arising from the finite element discretization of elliptic PDEs, is the problem considered here. A red-black ordering is introduced to increase the degree of parallelism of the computation. Space-time domain expansion techniques are used to partition the computation for a proposed fixed-size VLSI architecture.
References
[1]
H.D. Cheng and K.S. Fu, "Algorithm partition for a fixed size VLSI architecture using space-time domain expansion", Proc. 7th Symp. Comput. Arithmetic, June 1985, pp. 126-132.
[2]
H.D. Cheng and K.S. Fu, "VLSI architectures for pattern matching using spacetime domain expansion approach", October 1984, Purdue University.
[3]
H.D. Cheng and K.S. Fu, "Algorithm partition and parallel recognition of general context free languages using fixed size VLSI architecture", June 1984, Purdue University.
[4]
H.D. Cheng, W.C. Lin and K.S. Fu, "Space -time domain expansion approach to VLSI and its application to hierarchical scene matching", IEEE Trans. on Pattern Anal. Mach. Int., March 1985.
[5]
G. Gotub and D. Mayers, "The use of preconditioning over irregular regions", Num. Anal. Project Report No. NA-83-27, Stanford University, 1983.
[6]
A. Hadjidimos, "Accelerated Overrelaxation Method", Math. Comp. 32- 149-157, 1978.
[7]
A. Hadjidimos, T.S. Papatheodorou and Y.G. Saridakis, "Optimal block iterative schemes for certain large, sparse and nonsymmetric Linear Systems I", (to appear).
[8]
C.E. Houstis, E.N. Houstis and J.R. Rice, "Partitioning and allocation of PDE computations in distributed systems", Preprint 1984, Purdue University.
[9]
E.N. Houstis, R.E. Lynch, T.S. Papatheodorou and J.R. Rice, "Evaluation of numerical methods for elliptic partial differential equations", J. Comp. Phys. 27- 323-350, 1978.
[10]
K. Hwang and Y.H. Cheng, "Partitioned algorithms and VLSI structures for large-scale matrix computations", Proc. 5th Symp. Comput. Arithmetic, May 1981, pp. 222-232.
[11]
K. Hwang and Y.H. Cheng, "Partitioned Matrix Algorithms for VLSI Arithmetic systems", IEEE Trans. on Comp., C-31 (12): 1215-1224, 1982.
[12]
D.I. Moldovan and J.A.B. Fortes, "Partitioning and Mapping Algorithms into fixed size systolic arrays", IEEE Trans. on Comp., C-35(t)' 1-12, 1986.
[13]
D.I. Moldovan, C.I. Wu and J.A.B. Fortes, "Mapping an arbitrarily large QR algorithm into a fixed size VLSI array", Proc. of 1984 Int. Conf. on Parallel Processing, August 1984.
[14]
A. Noor, H. Kamel and R. Fulton, "Substructuring techniques-status and projection'', Computers and Structures, 8: 621-632, 1978.
[15]
J.M. Ortega and R.G. Voigt, "Solution of Partial Differential equations on vector and parallel computers", SIAM Review, 27(2)- 149-240, 1985.
[16]
E.P. Papadopoulou, "VLSI structures and iterative analysis for large scale computation", Ph.D. Thesis, Clarkson University, 1986.
[17]
T.S. Papatheodorou, "Inverses for a class of banded matrices and applications to piecewise cubic approximation'', J. of Comp. Appl. Math. 8(4), 1982.
[18]
T.S. Papatheodorou, "Block AOR Iteration for Nonsymmetric Matrices", Math. Comp. 41(164)' 511-525, 1983.
[19]
T.S. Papatheodorou, A. Hadjidimos and Y.G. Saridakis, "Optimal block iterarive schemes for certain large, sparse and nonsymmetric systems II, (to appear).
[20]
M.C. Peace, "Inversion of Matrices by Partitioning", J. of ACM, 16(2)- 302- 314, 1969.
[21]
J.R. Rice and R.F. Boisvert, "Solving Elliptic Problems using ELLPACK, Springer-Verlag, New York, 1984.
[22]
Y.G. Saridakis, "Parallelism, Applicability and Optimality of modern iterarive methods", Ph.D. Thesis, Clarkson University, 1985.
[23]
R.S. Varga, "p-Cyclic matrices' A generalization of the Young-Frankel Successive Overrelaxation Scheme", Pac. J. Math. 9' 617-628, 1959.
[24]
R.S. Varga, "Matrix Iterative Analysis'', Prentice-Hall, Englewood Cliffs, New Jersey, 1962.
[25]
O. Widlund, "Iterative methods for elliptic problems on regions partitioned into substructures and the biharmonic Dirichlet problem", CSR-101, Courant Institute, New York University, 1984.
[26]
D.M. Young, "Iterative Solution of Large Linear Systems", Academic Press, New York, 1971.
Index Terms
- Orderings and partition of PDE computations for a fixed-size VLSI architecture
Recommendations
Low-order dPG-FEM for an elliptic PDE
This paper introduces a novel lowest-order discontinuous PetrovGalerkin (dPG) finite element method (FEM) for the Poisson model problem. The ultra-weak formulation allows for piecewise constant and affine ansatz functions and for piecewise affine and ...
A New Formulation of the Mixed Finite Element Method for Solving Elliptic and Parabolic PDE with Triangular Elements
For the groundwater flow problem (which corresponds to the Darcy flow model), we show how to produce a scheme with one unknown per element, starting from a mixed formulation discretized with the Raviart Thomas triangular elements of lowest order. The ...
VLSI architecture for device simulation
In this paper, VLSI architectures for solving nonlinear equations are presented, such as the elliptic partial differential equations arising from semiconductor device modeling using a Newton-SOR (Successive Over Relaxation), finite difference, iterative ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 December 1987
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 99Total Downloads
- Downloads (Last 12 months)17
- Downloads (Last 6 weeks)6
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in