PYTHIA: a knowledge-based system to select scientific algorithms

ABSTRACT

Problem-solving environments (PSEs) interact with the user in a language “natural” to the associated discipline, and they provide a high-level abstraction of the underlying, computationally complex model. The knowledge-based system PYTHIA addresses the problem of (parameter, algorithm) pair selection within a scientific computing domain assuming some minimum user-specified computational objectives and some characteristics of the given problem. PYTHIA's framework and methodology are general and applicable to any class of scientific problems and solvers. PYTHIA is applied in the context of Parallel ELLPACK where there are many alternatives for the numerical solution of elliptic partial differential equations (PDEs). PYTHIA matches the characteristics of the given problem with those of PDEs in an existing problem population and then uses performance profiles of the various solvers to select the appropriate method given user-specified error and solution time bounds. The profiles are automatically generated for each solver of the Parallel ELLPACK library. —Authors' Abstract

REFERENCES

• 1: BAREISS, R. 1986. Exemplar-Based Knowledge Analysis. Academic Press, New York.
• 2: BOISVERT, R. F., RICE, J. R., AND HOUSTIS, E.N. 1979. A system for performance evaluation of partial differential equations software. IEEE Trans. Softw. Eng. SE-5, 4, 418-425.
• 3: Gail A. Carpenter , Stephen Grossberg, The ART of Adaptive Pattern Recognition by a Self-Organizing Neural Network, Computer, v.21 n.3, p.77-88, March 1988 [doi>10.1109/2.33]
• 4: DURBIN, R. AND WILLSttAW, D. 1987. An analogue approach to the travelling salesman problem using an elastic net method. Nature 326, 689-691.
• 5: DYKSEN, W. R., AND GRITTER, C. R. 1989. Elliptic expert: An expert system for elliptic partial differential equations. Math. Comput. Simul. 31, 333-343.
• 6: DYKSEN, W. R. AND GRITTER, C.R. 1992. Scientific computing and the algorithm selection problem. In Expert Systems for Scientific Computing, E. N. Houstis, J. R. Rice, and R. Vichnevetsky, Eds. North-Holland, Amsterdam, 19-31.
• 7: DYKSEN, W. R., RIBBENS, C. J., AND RICE, J.R. 1988. The performance of numerical methods for elliptic problems with mixed boundary conditions. Num. Meth. Partial Differential Equations 4, 347-361.
• 8: Efstratios Gallopoulos , Elias Houstis , John R. Rice, Computer as Thinker/Doer: Problem-Solving Environments for Computational Science, IEEE Computational Science & Engineering, v.1 n.2, p.11-23, June 1994 [doi>10.1109/99.326669]
• 9: GIARRATANO, J. C. 1991. CLIPS User's Guide. Ver. 5.1. NASA Lyndon B. Johnson Space Center, Houston, Tex.
• 10: HOLLANDER, M. AND WOLFE, D. 1973. Nonparametric Statistical Methods. John Wiley and Sons, New York.
• 11: HOPFIELD, J. J. AND TANK, D. 1986. Computing with neural circuits. Science 233, 625-633.
• 12: HOUSTIS, E. N. AND RICE, J. R. 1982. High order methods for elliptic partial differential equations with singularities. Int. J. Num. Meth. Eng. 18, 737-754.
• 13: E. N. Houstis , J. R. Rice , N. P. Chrisochoides , H. C. Karathanasis , P. N. Papachiou , M. K. Samartzis , E. A. Vavalis , Ko Yang Wang , S. Weerawarana, //ELLPACK: a numerical simulation programming environment for parallel MIMD machines, Proceedings of the 4th international conference on Supercomputing, p.96-107, June 11-15, 1990, Amsterdam, The Netherlands
• 14: E. N. Houstis , J. R. Rice , C. C. Christara , E. A. Vavalis, Performance of scientific software, Mathematical aspects of scientific software, Springer-Verlag New York, Inc., New York, NY, 1988
• 15: JOSHI, A., WEERAWARANA, S., AND HOUSTIS, E. N. 1994. The use of neural networks to support "intelligent" scientific computing. In Proceedings of the International Conference on Neural Networks, World Congress on Computational Intelligence. Vol. IV. 411-416.
• 16: Anupam Joshi , Sanjiva Weerawarana , Narendran Ramakrishnan , Elias N. Houstis , John R. Rice, Neuro-Fuzzy Support for Problem-Solving Environments: A Step Toward Automated Solution of PDEs, IEEE Computational Science & Engineering, v.3 n.1, p.44-56, March 1996 [doi>10.1109/99.486760]
• 17: M. S. Kamel , W. H. Enright , K. S. Ma, ODEXPERT: an expert system to select numerical solvers for initial value ODE systems, ACM Transactions on Mathematical Software (TOMS), v.19 n.1, p.44-62, March 1993 [doi>10.1145/151271.151275]
• 18: KONIG, S. AND ULLRICH, C. 1990. An expert system for the economical application of self-validating methods for linear equations. In Intelligent Mathematical Software Systems, E. N. Houstis, J. R. Rice, and R. Vichnevetsky, Eds. North-Holland, Amsterdam, 195-220.
• 19: MOORE, P. K., OZTURAN, C., AND FLAHERTY, J. E. 1990. Towards the automatic numerical soluti on of partial differential equations. In Intelligent Mathematical Software Systems, E. N. Houstis, J. R. Rice, and R. Vichnevetsky, Eds. North-Holland, Amsterdam, 15-22.
• 20: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 21: RICE, J.R. 1976. The algorithm selection problem. Adv. Comput. 15, 65-118.
• 22: RICE, J.R. 1979. Methodology for the algorithm selection problem. In Performance Evaluation of Numerical Software, L. D. Fosdick, Ed. North-Holland, Amsterdam, 301-307.
• 23: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 24: RICE, J. R., HOUSTIS, E. N., AND DYKSEN, W.R. 1981. A population of linear, second order, elliptic partial differential equations on rectangular domains, part I. Math. Comput. 36, 475-484.
• 25: David E. Rumelhart , James L. McClelland , CORPORATE PDP Research Group, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
• 26: Kai-Yeung Siu , Vwani Roychowdhury , Thomas Kailath, Discrete neural computation: a theoretical foundation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 27: Sanjiva Weerawarana , Elias N. Houstis, Problem-solving environments for partial differential equation based applications, 1994
• 28: WEERAWARANA, S., HOUSTIS, E. N., RICE, J. R., CATLIN, A. C., CRABILL, C. L., CHUI, C. C., AND MARKUS, S. 1994. PDELab: An object-oriented framework for building problem solving environments for PDE based applications. In Proceedings of the 2nd Annual Object-Oriented Numerics Conference. Rogue-Wave Software, Corvallis, Oreg., 79-92.
• 29: Bernard Widrow , Rodney Winter, Neural Nets for Adaptive Filtering and Adaptive Pattern Recognition, Computer, v.21 n.3, p.25-39, March 1988 [doi>10.1109/2.29]
• 30: ZELL, A., MACHE, N., HUB~mR, R., MAMIER, G., VOGT, M., HERRMANN, K.-U., SCHMALZL, M., SOMMER, T., HATZIGEORGIOU, A., DORING, S., AND POSSELT, D. 1993. Stuttgart Neural Network Simulator User Manual. Ver. 3.1. Tech. Rep. 3, Univ. of Stuttgart, Stuttgart, Germany.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations

General Terms:
Algorithms, Performance

Keywords:
computational intelligence, knowledge-based systems, partial differential equations, performance evaluation, problem-solving environments