Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-18T02:46:51.559Z Has data issue: false hasContentIssue false
  • English
  • Français

Sparse matrix representations in a functional language

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

P. W. Grant ,
J. A. Sharp ,
M. F. Webster  and
X. Zhang
P. W. Grant
Affiliation:
Department of Computer Science, University of Wales, Swansea, Swansea SA2 8PP, UK
J. A. Sharp
Affiliation:
Department of Computer Science, University of Wales, Swansea, Swansea SA2 8PP, UK
M. F. Webster
Affiliation:
Department of Computer Science, University of Wales, Swansea, Swansea SA2 8PP, UK
X. Zhang
Affiliation:
Department of Computer Science, University of Wales, Swansea, Swansea SA2 8PP, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper investigates several sparse matrix representation schemes and associated algorithms in Haskell for solving linear systems of equations arising from solving realistic computational fluid dynamics problems using a finite element algorithm. This work complements that of Wainwright and Sexton (1992) in that a Choleski direct solver (with an emphasis on its forward/backward substitution steps) is examined. Experimental evidence comparing time and space efficiency of these matrix representation schemes is reported, together with associated forward/backward substitution implementations. Our results are in general agreement with Wainwright and Sexton's.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 1 , January 1996 , pp. 143 - 170
Copyright
Copyright © Cambridge University Press 1996

References

Al-Hussany, A. F. H., Townsend, P. and Webster, M. F. (1993) Computer simulation of temperature build-up in the radial filling of disc-shaped cavities. In Proc. Computational Mechanics in UK, pp. 49–54. Swansea, UK, January 1993. Association for Computational Mechanics in Engineering, UK.Google Scholar
Augustsson, L. (1993) Haskell B user's manual. Department of Computer Sciences, Chalmers University of Technology, Sweden, October.Google Scholar
Cuvelier, C., Segal, A. and van Steenhoven, A. A. (1986) Finite Element Methods and Navier-Stokes Equations. Reidel Publishing Co.CrossRefGoogle Scholar
Davie, A. J. T. (1992) An Introduction to Functional Programming Systems Usin¨g Haskell. Cambridge University Press.Google Scholar
Ding, D., Townsend, P. and Webster, M. F. (1993) Computer modelling of transient thermal flows of non-Newtonian fluids. J. Non-Newtonian Fluid Mechanism, 47: 239–56.CrossRefGoogle Scholar
Duff, I. S., Erisman, A. M. and Reid, J. K. (1986) Direct Methods for Sparse Matrices. Clarendon Press.Google Scholar
Grant, P. W., Sharp, J. A., Webster, M. F. and Zhang, X. (1992) A Haskell implementation of a Generalized Envelope method for sparse matrix factorization. In Proc. ATABLE-92, pp. 247–260. Montreal, Canada, June.Google Scholar
Grant, P. W., Sharp, J. A., Webster, M. F. and Zhang, X. (1993a) Functional programming for a computational fluid dynamics problem. In Proc. Computational Mechanics in UK, pp. 75–79. Swansea, UK, January. Association for Computational Mechanics in Engineering, UK.Google Scholar
Grant, P. W., Sharp, J. A., Webster, M. F. and Zhang, X. (1993b) Some issues in a functional implementation of a finite element algorithm. In Proc. FPCA '93, pp. 12–17. Copenhagen, Denmark, June. ACM SIGPLAN/SIGARCH.CrossRefGoogle Scholar
Grant, P. W., Sharp, J. A., Webster, M. F. and Zhang, X. (1994) Experiences of parallelising finite element problems in a functional style. Software – Practice and Experience, to appear.CrossRefGoogle Scholar
Hageman, L. A. and Young, D. M. (1981) Applied Iterative Methods. Academic Press.Google Scholar
Hawken, D. M., Tamaddon-Jahromi, H. R., Townsend, P. and Webster, M. F. (1990) A Taylor-Galerkin-based algorithm for viscous incompressible flow. Int. J. Num. Meth. Fluids, 10: 327–351.CrossRefGoogle Scholar
Hudak, P., Peyton Jones, S. L. and Wadler, P., editors (1992) Report on the Programming Language Haskell, A Non-strict Purely Functional Language (Version 1.2). SIGPLAN Notices, May.Google Scholar
Liu, J. W. H. (1986) A compact row storage scheme for Choleski factors using elimination trees. ACM Trans. Math. Software, 12: 127–148. June.CrossRefGoogle Scholar
Liu, J. W. H. (1991) A generalized envelope method for sparse factorization by rows. ACM Trans. Math. Software, 17: 112–129. March.CrossRefGoogle Scholar
Peyton Jones, S. L., Launchbury, J. and Partain, W. (1994) GHC prelude: Types and operations. Technical report, Computing Science Department, Glasgow University.Google Scholar
Peyton Jones, S. L. and Wadler, P. (1993) Imperative functional programming. In ACM Symposium on Principles of Programming Languages, pp. 71–84. Charleston, SC, January.CrossRefGoogle Scholar
Runciman, C. and Wakeling, D. (1993) Heap profiling for lazy functional languages. J. Functional Programming, 3(2): 217–245. April.CrossRefGoogle Scholar
Sansom, P. M. and Peyton Jones, S. L. (1992) Pyrofiling lazy functional programs. In Proc. Functional Programming, Glasgow. Workshops in Computing. Springer-Verlag.Google Scholar
Spivey, M. (1990) A functional theory of exceptions. Science of Computer Programming, 14(1): 25–42. June.CrossRefGoogle Scholar
Townsend, P. and Webster, M. F. (1987) An algorithm for the three-dimensional transient simulation of non-Newtonian fluid flows. In Pande, G. N. and Middleton, J., editors, Proc. Int. Conf. Num. Meth. Eng.: Theory and Applications, II, pp. T12/1–11. Swansea, UK. NUMETA, Nijhoff, Dordrecht.Google Scholar
Wainwright, R. L. and Sexton, M. E. (1992) A study of sparse matrix representations for solving linear systems in a functional language. J. Functional Programming, 2(1): 61–72. January.CrossRefGoogle Scholar
Wilkinson, J. H. and Reinsch, C. (1971) Handbook for Automatic Computation, Linear Algebra, vol. II. Springer-Verlag.CrossRefGoogle Scholar
Wise, D. S. (1992) Matrix algorithms using quadtrees (invited talk). In Proc. ATABLE-92, pp. 11–26. Montreal, Canada, June.Google Scholar
Zhang, X., Webster, M. F., Sharp, J. A. and Grant, P. W. (1994a) Computational fluid dynamics application. In Runciman and, C.Wakeling, D., editors, Applied Functional Programming, chap. 9. UCL Press.Google Scholar
Zhang, X., Webster, M. F., Sharp, J. A. and Grant, P. W. (1994b) Parallelisation for computational fluid dynamics. In Runciman, C. and Wakeling, D., editors, Applied Functional Programming, chap. 12. UCL Press.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.