Graph based isomorph-free generation of two-level regular fractional factorial designs. (English) Zbl 1178.62082
Summary: We provide a new necessary and sufficient check for testing the isomorphism of two 2-level regular fractional factorial designs. The approach is based on modeling fractional factorial designs as bipartite graphs. We employ an efficient canonical graph labeling approach to compare two designs for isomorphism. We then improve upon the existing non-isomorphic fractional factorial design generation algorithm by reducing the number of candidate designs from which isomorphs need to be removed. Not only does our method generate non-isomorphic designs much faster, it is also able to generate designs with run sizes of 2048 and 4096 runs, which were not generated by the existing methods.
MSC:
| 62K15 | Factorial statistical designs |
| 05C90 | Applications of graph theory |
| 65C60 | Computational problems in statistics (MSC2010) |
Keywords:
isomorphism; graphs; design catalog; automorphism; large designs; defining contrast subgroup; treatment combinations subgroup; canonical labelingReferences:
| [1] | Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D., 1999. LAPACK Users’ Guide, third ed. Society for Industrial and Applied Mathematics, Philadelphia, PA.; Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D., 1999. LAPACK Users’ Guide, third ed. Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0934.65030 |
| [2] | Bailey, R. A., Patterns of confounding in factorial designs, Biometrika, 64, 3, 597-603 (1977) · Zbl 0376.62052 |
| [3] | Bingham, D.; Sitter, R. R., Minimum-aberration two-level fractional factorial split-plot designs, Technometrics, 41, 1, 62-70 (1999) |
| [4] | Box, G. E.P.; Hunter, J. S., The \(2^{k - p}\) fractional factorial designs. Part I, Technometrics, 3, 3, 311-351 (1961) · Zbl 0100.14406 |
| [5] | Box, G. E.P.; Hunter, J. S., The \(2^{k - p}\) fractional factorial designs. Part I, Technometrics, 42, 1, 28-47 (2000) · Zbl 0100.14406 |
| [6] | Cameron, P.; Mary, Q., Automorphisms of graphs, (Beineke, L. W.; Wilson, R. J.; Cameron, P. J., Topics in Algebraic Graph Theory. Encyclopedia of Mathematics and its Applications, vol. 102 (2004), Cambridge University Press: Cambridge University Press Cambridge), 137-155 · Zbl 1061.05044 |
| [7] | Chen, J., Some results on \(2^{n - k}\) fractional factorial designs and search for minimum aberration designs, The Annals of Statistics, 20, 4, 2124-2141 (1992) · Zbl 0770.62063 |
| [8] | Chen, J.; Sun, D. X.; Wu, C. F.J., A catalogue of two-level and three-level fractional factorial designs with small runs, International Statistical Review, 61, 1, 131-145 (1993) · Zbl 0768.62058 |
| [9] | Cheng, S.-W.; Ye, K. Q., Geometric isomorphism and minimum aberration for factorial designs with quantitative factors, The Annals of Statistics, 32, 5, 2168-2185 (2004) · Zbl 1056.62088 |
| [10] | Clark, J. B.; Dean, A. M., Equivalence of fractional factorial designs, Statistica Sinica, 11, 537-547 (2001) · Zbl 0980.62058 |
| [11] | Draper, N. R.; Mitchell, T. J., The construction of saturated \(2_r^{k - p}\) designs, The Annals of Mathematical Statistics, 38, 4, 1110-1126 (1967) · Zbl 0158.37404 |
| [12] | Draper, N. R.; Mitchell, T. J., Construction of a set of 512-run designs of resolution 5 and a set of even 1024-run designs of resolution 6, The Annals of Mathematical Statistics, 41, 3, 876-887 (1970) · Zbl 0227.62046 |
| [13] | Fortin, S., 1996. The graph isomorphism problem. Technical Report TR 96-20, Department of Computer Science, The University of Alberta, Edmonton, Alberta, Canada.; Fortin, S., 1996. The graph isomorphism problem. Technical Report TR 96-20, Department of Computer Science, The University of Alberta, Edmonton, Alberta, Canada. |
| [14] | Katsaounis, T.; Dean, A., A survey and evaluation of methods for determination of combinatorial equivalence of factorial designs, Journal of Statistical Planning and Inference, 138, 1, 245-258 (2008) · Zbl 1130.62077 |
| [15] | Kocay, W., On writing isomorphism programs, (Wallis, W. D., Computational and Constructive Design Theory, vol. 368 (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands), 135-175 · Zbl 0851.68087 |
| [16] | Lawson, C.; Hanson, R.; Kincaid, D.; Krogh, F., Basic linear algebra subprograms for Fortran usage, ACM Transactions on Mathematical Software (TOMS), 5, 3, 308-323 (1979) · Zbl 0412.65022 |
| [17] | Lin, C. D.; Sitter, R. R., An isomorphism check for two-level fractional factorial designs, Journal of Statistical Planning and Inference, 138, 4, 1085-1101 (2008) · Zbl 1130.62078 |
| [18] | Ma, C. X.; Fang, K. T.; Lin, D. K.J., On the isomorphism of fractional factorial designs, Journal of Complexity, 17, 1, 86-97 (2001) · Zbl 0979.62055 |
| [19] | McKay, B. D., Practical graph isomorphism, Congressus Numerantium, 30, 1, 45-87 (1981) · Zbl 0521.05061 |
| [20] | McKay, B. D., Isomorph-free exhaustive generation, Journal of Algorithms, 26, 2, 306-324 (1998) · Zbl 0894.68107 |
| [21] | McKay, B.D., 2004. nauty User’s Guide (Version 2.2). Computer Science Department, Australian National University, ACT 0200, Australia. URL: \( \langle;\) http://cs.anu.edu.au/people/Brendan.McKay/nauty/nug.pdf \(\rangle;\).; McKay, B.D., 2004. nauty User’s Guide (Version 2.2). Computer Science Department, Australian National University, ACT 0200, Australia. URL: \( \langle;\) http://cs.anu.edu.au/people/Brendan.McKay/nauty/nug.pdf \(\rangle;\). |
| [22] | Read, R. C.; Corneil, D. G., The graph isomorphism disease, Journal of Graph Theory, 1, 1, 339-363 (1977) · Zbl 0381.05026 |
| [23] | Stimming, C., \(2007. \operatorname{Lapack} ++ 2.5.2\). URL: \( \langle;\) http://lapackpp.sourceforge.net/\( \rangle;\).; Stimming, C., \(2007. \operatorname{Lapack} ++ 2.5.2\). URL: \( \langle;\) http://lapackpp.sourceforge.net/\( \rangle;\). |
| [24] | Sun, D.X., Li, W., Ye, K.Q., 2002. An algorithm for sequentially constructing non-isomorphic orthogonal designs and its applications. Technical Report SUNYSB-AMS-02-13, Department of Applied Mathematics and Statistics, Stony Brook University, New York.; Sun, D.X., Li, W., Ye, K.Q., 2002. An algorithm for sequentially constructing non-isomorphic orthogonal designs and its applications. Technical Report SUNYSB-AMS-02-13, Department of Applied Mathematics and Statistics, Stony Brook University, New York. |
| [25] | Wu, C. F.J.; Hamada, M., Experiments: Planning, Analysis, and Parameter Design Optimization. Wiley Series in Probability and Statistics (2000), Wiley: Wiley New York · Zbl 0964.62065 |
| [26] | Xu, H., A catalogue of three-level regular fractional factorial designs, Metrika, 62, 2, 259-281 (2005) · Zbl 1078.62084 |
| [27] | Zhu, Y.; Zeng, P., On the coset pattern matrices and minimum m-aberration of \(2^{n - p}\) designs, Statistica Sinica, 15, 3, 717 (2005) · Zbl 1086.62086 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
