Note on generalization in experimental algorithmics

ABSTRACT

A recurring theme in mathematical software evaluation is the generalization of rankings of algorithms on test problems to build knowledge-based recommender systems for algorithm selection. A key issue is to profile algorithms in terms of the qualitative characteristics of benchmark problems. In this methodological note, we adapt a novel all-pairs algorithm for the profiling task; given performance rankings for m algorithms on n problem instances, each described with p features, identify a (minimal) subset of p that is useful for assessing the selective superiority of an algorithm over another, for all pairs of m algorithms. We show how techniques presented in the mathematical software literature are inadequate for such profiling purposes. In conclusion, we also address various statistical issues underlying the effective application of this technique.

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: BOISVERT,R.F.,HOUSTIS,E.N.,AND RICE, J. R. 1979. A system for performance evaluation of partial differential equations software. IEEE Trans. Softw. Eng. SE-5, 4 (July), 418-425.
• 3: Harlan Crowder , Ron S. Dembo , John M. Mulvey, On Reporting Computational Experiments with Mathematical Software, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.193-203, June 1979 [doi>10.1145/355826.355833]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: HOLLANDER,M.AND WOLFE, D. 1973. Nonparametric Statistical Methods. John Wiley and Sons, Inc., New York, NY.
• 6: HOUSTIS,E.AND RICE, J. 1982. High order methods for elliptic partial differential equations with singularities. Int. J. Numer. Method. Eng. 18, 737-754.
• 7: 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]
• 8: Brian H LaRose, The Development and Implementation of a Performance Database Server, University of Tennessee, Knoxville, TN, 1993
• 9: 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]
• 10: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 11: Narendran Ramakrishnan , Elias N. Houstis, Recommender systems of problem-solving environments, 1997
• 12: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 13: RICE, J., HOUSTIS, E., AND DYKSEN, W. 1981. A population of linear, second order, elliptic partial differential equations on rectangular domains: part I. Math. Comput. 36, 475-484.
• 14: Raúl E. Valdés-Pérez, Principles of human-computer collaboration for knowledge discovery in science, Artificial Intelligence, v.107 n.2, p.335-346, Feb. 1999 [doi>10.1016/S0004-3702(98)00116-7]
• 15: Raúl E. Valdéz-Pérez , Francisco Pereira, Concise, intelligible, and approximate profiling of multiple classes, International Journal of Human-Computer Studies, v.53 n.3, p.411-436, Sept. 2000 [doi>10.1006/ijhc.2000.0397]
• 16: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

General Terms:
Algorithms, Performance

Keywords:
benchmark studies, experimental algorithmics, performance evaluation, profiling