Mining and visualizing recommendation spaces for elliptic PDEs with continuous attributes

ABSTRACT

In this paper we extend previous work in mining recommendation spaces based on symbolic problem features to PDE problems with continuous-valued attributes. We identify the research issues in mining such spaces, present a dynamic programming algorithm form the data-mining literature, and describe how a priori domain metaknowledge can be used to control the complexity of induction. A visualization aid for continuous-valued recommendation spaces is also outlined. Two case studies are presented to illustrate our approach and tools: (i) a comparison of an iterative and a direct linear system solver on nearly singular problems, and (ii) a comparison of two iterative solvers on problems posed on nonrectangular domains. Both case studies involve continuously varying problem and method parameters which strongly influence the choice of best algorithm in particular cases. By mining the results from thousands of PDE solves, we can gain valuable insight into the relative performance of these methods on similar problems.

REFERENCES

• 1: C. A. Addison , W. H. Enright , P. W. Gaffney , I. Gladwell , P. M. Hanson, Algorithm 687: a decision tree for the numerical solution of initial value ordinary differential equations, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.1-10, March 1991 [doi>10.1145/103147.103148]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 4: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 5: Jon Bentley, Programming pearls, ACM Press, New York, NY, 1986
• 6: BOISVERT, R., RICE, J., AND HOUSTIS, E. 1979. A System for Performance Evaluation of Partial Differential Equations Software. IEEE Transactions on Software Engineering Vol. SE-5, 4 (July), pp. 418-425.
• 7: E. de Sturler, A performance model for Krylov subspace methods on mesh-based parallel computers, Parallel Computing, v.22 n.1, p.57-74, Jan. 1996 [doi>10.1016/0167-8191(95)00057-7]
• 8: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada
• 9: Anne Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 10: Jiawei Han , Laks V. S. Lakshmanan , Raymond T. Ng, Constraint-Based, Multidimensional Data Mining, Computer, v.32 n.8, p.46-50, August 1999 [doi>10.1109/2.781634]
• 11: Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999 [doi>10.1109/2.781635]
• 12: Christian Hidber, Online association rule mining, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.145-156, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 13: E. N. Houstis , J. R. Rice , S. Weerawarana , A. C. Catlin , P. Papachiou , K.-Y. Wang , M. Gaitatzes, PELLPACK: a problem-solving environment for PDE-based applications on multicomputer platforms, ACM Transactions on Mathematical Software (TOMS), v.24 n.1, p.30-73, March 1998 [doi>10.1145/285861.285864]
• 14: Elias N. Houstis , Ann C. Catlin , John R. Rice , Vassilios S. Verykios , Naren Ramakrishnan , Catherine E. Houstis, PYTHIA-II: a knowledge/database system for managing performance data and recommending scientific software, ACM Transactions on Mathematical Software (TOMS), v.26 n.2, p.227-253, June 2000 [doi>10.1145/353474.353475]
• 15: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 16: 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]
• 17: Michael Lucks , Ian Gladwell, Automated selection of mathematical software, ACM Transactions on Mathematical Software (TOMS), v.18 n.1, p.11-34, March 1992 [doi>10.1145/128745.128747]
• 18: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 19: MITCHELL, T. M. 1982. Generalization as Search. Artificial Intelligence 18, 2, pp. 203-226.
• 20: Lucille Terry Nowell , Deborah Hix, Graphical encoding for information visualization: using icon color, shape, and size to convey nominal and quantitative data, 1997
• 21: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 22: Claude Pommerell , Wolfgang Fichtner, Memory aspects and performance of iterative solvers, SIAM Journal on Scientific Computing, v.15 n.2, p.460-473, March 1994 [doi>10.1137/0915031]
• 23: RAMAKRISHNAN, N. 1999. Experiences with an Algorithm Recommender System. In P. Baudisch Ed., Proceedings of the CHI'99 Workshop on Recommender Systems. ACM SIGCHI Press.
• 24: Naren Ramakrishnan , Ananth Y. Grama, Data Mining-Guest Editors' Introduction: From Serendipity to Science, Computer, v.32 n.8, p.34-37, August 1999 [doi>10.1109/2.781632]
• 25: Naren Ramakrishnan , Raúl E. Valdés-Pérez, Note on generalization in experimental algorithmics, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.568-580, Dec. 2000 [doi>10.1145/365723.365734]
• 26: RIBBENS,C.J.AND RICE, J. R. 1986. Realistic PDE Solutions for Non-Rectangular Domains. Technical Report CSD-TR-639, Department of Computer Sciences, Purdue University, West Lafayette, IN.
• 27: RICE, J. 1976. The Algorithm Selection Problem. Advances in Computers 15, pp. 65-118. Academic Press, New York.
• 28: John R. Rice, Algorithm 625: A Two-Dimensional Domain Processor, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.453-462, Dec. 1984 [doi>10.1145/2701.356110]
• 29: RICE, J., HOUSTIS, E., AND DYKSEN, W. 1981. A Population of Linear, Second Order, Elliptic Partial Differential Equations on Rectangular Domains, Part I. Mathematics of Computa-tion 36, pp. 475-484.
• 30: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 31: SAAD, Y. 1990. SPARSKIT: A Basic Tool Kit for Sparse Matrix Computations. Technical Report 90-20, Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffet Field, CA.
• 32: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 33: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 34: SCHMID, W., PAFFRATH, M., AND HOPPE, R. H. W. 1995. Application of Iterative Methods for Solving Nonsymmetric Linear Systems in the Simulation of Semiconductor Processing. Surv. Math. Indust. 5, pp. 1-26.
• 35: SMALLMAN,H.S.AND BOYNTON, R. M. 1990. Segregation of Basic Colors in an Information Display. Journal of the Optical Society of America 7, 102, pp. 1985-1994.
• 36: STEINACHER, S. 1998. Data Mining: What Your Data Would Tell You if It Could Talk. http://news400.com.
• 37: SUBRAMANIAN,D.AND FEIGENBAUM, J. 1986. Factorization in Experiment Generation. Pro-ceedings of the National Conference on Artificial Intelligence (AAAI'86), pp. 518-522.
• 38: Sanjiva Weerawarana , Elias N. Houstis , John R. Rice , Anupam Joshi , Catherine E. Houstis, PYTHIA: a knowledge-based system to select scientific algorithms, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.447-468, Dec. 1996 [doi>10.1145/235815.235820]
• 39: ZHANG, J. 1996. Preconditioned Krylov Subspace Methods for Solving Nonsymmetric Matri-ces from CFD Applications. Technical Report 280-98, Department of Computer Science, University of Kentucky, Lexington, KY. To appear in Computer Methods in Applied Mechanics and Engineering.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Performance, Theory

Keywords:
associations, data mining, performance evaluation, recommender systems