Performance Boundaries for Interactive Finite Element Applications

This paper presents work characterizing finite element performance boundaries within which live, interactive finite element modeling is feasible on current and emerging systems. These results are based on wide-ranging tests performed using a prototype finite element program implemented specifically for this study, thereby enabling the unified investigation of numerous direct and iterative solver strategies and implementations in a variety of modeling contexts. The results are intended to be useful for researchers interested in interactive analysis by providing baseline performance estimates, to give guidance in matching solution strategies to problem domains, and to spur further work addressing the challenge of extending the present boundaries.

Authors:

• Jaewon Jang
• Gregory R. Miller

Keywords:

• Finite Elements
• Interactive Modeling
• NumericalAnalysis.

References:

[1] A. Lindblad, "Increasing the functionality of finite element based surgical
suturing simulators," Ph.D. dissertation, University of Washington,
2006.
[2] A. George and J. W.-H. Liu, Computer solution of large sparse positive
definite systems. Prentice Hall, Inc., 1981.
[3] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra,
V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the
solution of linear systems: Building blocks for iterative methods, 2nd ed.
Siam, 1994.
[4] J. W. Demmel, Applied numerical linear algebra. Siam, 1997.
[5] W. L. Briggs, V. E. Henson, and S. F. McCormick, A multigrid tutorial,
2nd ed. Siam, 2000.
[6] Y. Saad, Iterative methods for sparse linear systems, 2nd ed. Siam,
2003.
[7] E. Cuthill and J. McKee, "Reducing the bandwidth of sparse symmetric
matrices," in Proc. 24th Nat. Conf. ACM, 1969, pp. 157-172.
[8] P. R. Amestoy, T. A. Davis, and I. S. Duff, "An approximate minimum
degree ordering algorithm," Siam J. Matrix Anal. Appl., vol. 17, no. 4,
pp. 886-905, 1996.
[9] G. Karypis, METIS, http://glaros.dtc.umn.edu/gkhome/metis/metis/overview,
2006.
[10] G. R. Miller, P. Arduino, J. Jang, and C. Choi, "Localized tensor-based
solvers for interactive finite element applications using C++ and Java,"
Comput. Struct., vol. 81, no. 7, pp. 423-437, 2003.
[11] M. D. Rucki and G. R. Miller, "An algorithmic framework for flexible
finite element-based structural modeling," Comp. Meth. Appl. Mech.
Engrg., vol. 36, no. 3-4, pp. 363-384, 1996.
[12] G. R. Miller, "Coordinate-free isoparametric elements," Comput. Struct.,
vol. 49, pp. 1027-1035, 1993.
[13] R. C. Whaley, A. Petitet, and J. J. Dongarra, "Automated empirical
optimizations of software and the ATLAS project," Parallel Comput.,
vol. 27, no. 1-2, pp. 3-35, 2001.
[14] K. Goto, GotoBLAS, Texas Advanced Computing
Center, Univ. of Texas at Austin, 2006,
http://www.tacc.utexas.edu/resources/software/software.php.
[15] K. A. Remington and R. Pozo, NIST Sparse BLAS, National Institute of
Standards and Technology, 1996, http://math.nist.gov/spblas.
[16] J. J. Dongarra, Basic linear algebra subprograms technical
(BLAST) forum standard, Univ. of Tennessee, Knoxville, Aug.
2001, http://www.netlib.org/blas/blast-forum/.
[17] E. Anderson, Z. Bai, C. Bischof, S. Blackford, and J. Demmel, LAPACK
users- guide, 3rd ed., Siam, 1999, http://www.netlib.org/lapack/.
[18] P. R. Amestoy, T. A. Davis, and I. S. Duff, AMD version 2.0 user
guide, Dept. of Computer and Information Science, Univ. of Florida,
2006, http://www.cise.ufl.edu/research/sparse/amd.
[19] T. A. Davis and W. W. Hager, "Dynamic supernodes in
sparse cholesky update/downdate and triangular solves," CISE
Dept, Univ. of Florida, Tech. Rep. TR-2006-004, 2006,
http://www.cise.ufl.edu/research/sparse/cholmod.
[20] T. A. Davis, UMFPACK version 5.0 user guide, Dept. of Computer
and Information Science, Univ. of Florida, May. 2006,
http://www.cise.ufl.edu/research/sparse/umfpack.
[21] J. W. Demmel, J. R. Gilbert, and X. S. Li, SuperLU user-s guide,
Univ. of California at Berkeley, 1999, http://www.cs.berkeley.edu/ demmel/
SuperLU.html.
[22] S. Balay, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik,
M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang, "PETSc
users manual," Argonne National Laboratory, Tech. Rep. ANL-95/11 -
Revision 2.1.5, 2004.
[23] J. W. Jang, "Characterization of live modeling performance boundaries
for computational structural mechanics," Ph.D. dissertation, University
of Washington, 2007.
[24] S. S. Skiena, The algorithm design manual. Springer-Verlag New York,
Inc., 1998.
[25] D. A. Patterson and J. L. Hennessy, Computer organization and design:
The hardware/software interface, 3rd ed. Morgan Kaufmann Publishers,
2005.
[26] SPEC Team, SPEC CPU2000 v1.3 documentation, Standard Performance
Evaluation Corporation, 2001, http://www.spec.org/cpu2000.
[27] C. A. Felippa, "A study of optimal membrane triangles with drilling
freedoms," University of Colorado, Tech. Rep. CU-CAS-03-02, 2003.
[28] H. Si, TetGen: A quality tetrahedral mesh generator and
three-dimensional delaunay triangulator version 1.4, Jan. 2006,
http://tetgen.berlios.de/.
[29] S. Balay, K. Buschelman, W. D. Gropp, D. Kaushik, M. G. Knepley,
L. C. McInnes, B. F. Smith, and H. Zhang, "PETSc Web page," 2001,
http://www.mcs.anl.gov/petsc.
[30] D. Bailey, T. Harris, and W. Saphir, "The NAS parallel benchmark 2.0,"
NASA Ames Research Center, Tech. Rep. NAS-95-020, 1995.
[31] S. W. Key and C. C. Hoff, "An improved constant membrane and
bending stress shell element for explicit transient dynamics," Comp.
Meth. Appl. Mech. Engrg., vol. 124, pp. 33-47, 1995.