Generating synthetic test matrices as a benchmark for the computational behavior of typical testor-finding algorithms

摘要

Each typical testor-finding algorithm has a specific sensibility towards the number of rows, columns or typical testors within its input matrix. In this research a theoretical framework and a practical strategy for designing test matrices for typical testor-finding algorithms is presented. The core of the theoretical framework consists on a set of operators that allow the generation of basic matrices with controlled dimensions and for which the total number of typical testors is known in advance. After presenting the required theoretical foundation, and the logic for measuring a testor-finding algorithm's computational behavior, the proposed strategy is used to assess the behavior of three well-known algorithms: BT, LEX, and FastCTExt. Unexpected behaviors, observed during the test experiments, are analyzed and discussed, revealing previously unknown characterizations of the tested algorithms that neither a complexity analysis, nor a random experimentation protocol could have revealed beforehand. (C) 2016 Elsevier B.V. All rights reserved.