NOA: Program for Constructing Orthogonal Arrays, Near-Orthogonal Arrays and Supersaturated Designs

1. Introduction
2. Using noa
3. Output
4. Examples
5. References

Introduction

In a near-OA L'_n(s₁...s_k), to reduce the run size, the orthogonality of some pairs of columns is necessarily sacrificed. The concept of near-OA (see Taguchi 1959; Wang and Wu 1992; Nguyen 1996b; Wu & Hamada 2000; Ma et. al. 2000 and Xu 2002) provides a genuine answer to situations when OAs are not available. An array is called a saturated design when ∑(s_i-1)=n-1 (e.g. a Hadamard matrix) and is called a supersaturated design when ∑(s_i-1)>n-1. The 2-level supersaturated designs were discussed in Booth & Cox (1962), Lin (1993), Nguyen (1996a), Tang & Wu (1997), Cheng (1997) and Wu & Hamada (2000) Section 8.6. The mixed level supersaturated designs were discussed in Fang, et. al. (2003, 2004). Additional references on this subject can be found in the references of these two papers.

NOA is a Gendex module for constructing mixed level OA, near-OAs and supersaturated designs. NOA is extremely useful when you want to augment OAs or near-OAs with additional columns. Several new OAs can be obtained by adding additional columns to the Sloane OA library. The first optimality criterion used in NOA, called the average criterion is the minimization of E(d²)=∑d²_ij /_kC₂ discussed Ma et. al (2000), Lu et. al. (2003) and Fang, et. al. (2003, 2004) (note that E(d²) is D² in the first reference and E(f_NOD) in the last two references). The second criterion, called the minimax criterion is close but not identical to the the max(d²) criterion discussed in Lu et. al. (2003). The following matrix shows the frequency distribution of the levels of the columns of an L'₈₄(3¹6¹)

5       4       5       5       4       5
4       5       5       4       5       5
5       5       4       5       5       4

which say the combination (0,0) appears 5 times and the combination (0,1) appears 4 times, etc. The expected frequency for each level combination is

n/(s₁s₂)=84/(2x6)=4.6667. The differences between the observed and the expected frequencies of each cell are in the following matrix:

 0.3333  -0.6667   0.3333   0.3333  -0.6667   0.3333
-0.6667   0.3333   0.3333  -0.6667   0.33333   0.3333
 0.3333   0.3333  -0.6667   0.3333   0.3333  -0.6667

Here d²₁₂ (=4) is defined as the squared Euclidean distance between the observed and expected frequencies (or the sum of squares of the values in the difference matrix). NOA's average criterion minimizes this d² value and NOA's minimax criterion minimizes the frequency of values which equal the maximum absolute value in the difference matrix (this value should be ≥1) . Details of the NOA algorithm which uses the mentioned optimality criteria is discussed Nguyen & Liu (2007).

Using NOA

Let's assume all Gendex class files are in the directory c:\gendex and suppose you want to construct an L₁₂(3¹2⁴). At the working directory, type the following command at the command prompt (case is important):

java -cp c:\gendex noa 

The NOA window will pop up. Enter the the number of factors at the appropriate levels and the number of runs (i.e. 12) and click START, the NOA window will become:

and the OUTPUT window showing an L₁₂(3¹2⁴) will pop up. Note that the START button has been changed to the STOP one. If you close the pop-up window, the STOP button will become a RESET one. If you click this RESET button, the output will disappear and you can use NOA for a new design problem. Also note that the default random seed is the one obtained from the system clock and the default number of tries is 100. You can change these default values if you wish to.

Now, suppose you want to construct an L₁₂(3¹2⁹) by adding five 2-level columns to an array L₁₂(3¹2⁹) obtained in the previous NOA session and stored in a file called base.txt:

2  0  1  0  1  
2  1  0  0  0  
0  0  1  1  0  
1  1  0  1  1  
2  0  0  1  0  
0  1  0  0  1  
0  1  1  0  0  
0  0  0  1  1  
1  0  1  0  1  
1  0  0  0  0  
2  1  1  1  1  
1  1  1  1  0  

Enter base.txt at the File text field and enter 5 at the 2-level text field of the NOA window and click START, the NOA window will become:

Output

The output message containing the result of the best try will appear in your window screen and is also saved in the file noa.htm in the working directory. Information for this try includes:

1. Try number;
2. The random seed used;
3. The number of iterations;
4. f =∑d²_ij if the average criterion is used or f (or frequency of values which equals the maximum absolute value ≥1 in the difference matrix if the minimax criterion is used) and g defined previously;
5. E(d²) and its lower bound. NOA bound improves the one of Fang, et. al. (2003, 2004) when the constructed design is a near-OA. Also, unlike the latter, the former does not make the restriction that n should be divisible by s_i (i=1,...,k). Details of the calculation of this lower bound will appear elsewhere. Note that for 2-level column arrays, the popular criterion E(s²)=4E(d²) (Eq. (14) of Fang, et. al. (2003)).
6. The frequency of d_ij=d_max;
7. N_p (the number of d_ij>0 or the number of pairs of nonorthogonal columns in the array).
8. A₂ (measurement of the overall aliasing or nonorthogonality between all possible pairs of columns).
9. D-efficiency;
10. The array;
11. The d² matrix;
12. The Cramer's V matrix: Cramer's V is the most popular of the chi-square-based measures of association between two nominal variables.
13. The number of protected columns if any;
14. The time in seconds NOA used to construct the above design.

Note: The calculations of items 7, 8 and 9 are in Section 2.2 of Xu (2002). Items 12 and 13 are not printed when the constructed array is an OA.

Examples

1. An L₁₂(3¹2⁴) (http://designcomputing.net/gendex/noa/m1.html).
2. An L₁₈(2¹3⁷) (http://designcomputing.net/gendex/noa/m2.html).
3. An L₂₀(5¹2⁸) (http://designcomputing.net/gendex/noa/m3.html).
4. An L₂₅(5⁶) (http://designcomputing.net/gendex/noa/m4.html).
5. An L₆₀(2¹⁵6¹10¹) (http://designcomputing.net/gendex/noa/m5.html).
6. An L₈₄(2¹⁴6¹14¹)(http://designcomputing.net/gendex/noa/m6.html).
7. An L'₆(3¹2³) (http://designcomputing.net/gendex/noa/n1.html).
8. An L'₁₀(5¹2⁵) (http://designcomputing.net/gendex/noa/n2.html).
9. An L'₁₂(4¹3⁴) (http://designcomputing.net/gendex/noa/n3.html).
10. An L'₁₂(2³3⁴) (http://designcomputing.net/gendex/noa/n4.html).
11. An L'₁₂(6¹2⁵) (http://designcomputing.net/gendex/noa/n5.html).
12. An L'₁₂(6¹2⁶) (http://designcomputing.net/gendex/noa/n6.html).
13. An L'₁₂(3¹2⁹) (http://designcomputing.net/gendex/noa/n7.html).
14. An L'₁₂(2¹3⁵) (http://designcomputing.net/gendex/noa/n8.html).
15. An L'₁₂(3²2⁷) (http://designcomputing.net/gendex/noa/n9.html).
16. An L'₁₂(3²2⁷) (http://designcomputing.net/gendex/noa/n9bis.html).
17. An L'₁₂(2⁵3³) (http://designcomputing.net/gendex/noa/n10.html).
18. An L'₁₅(5¹3⁵) (http://designcomputing.net/gendex/noa/n11.html).
19. An L'₁₈(2¹3⁸) (http://designcomputing.net/gendex/noa/n12.html).
20. An L'₁₈(3⁷2³) (http://designcomputing.net/gendex/noa/n13.html).
21. An L'₁₈(9¹2⁸) (http://designcomputing.net/gendex/noa/n14.html).
22. An L'₂₀(5¹2¹⁵) (http://designcomputing.net/gendex/noa/n15.html).
23. An L'₂₄(8¹3⁸) (http://designcomputing.net/gendex/noa/n16.html).
24. An L'₂₄(3¹2²¹) (http://designcomputing.net/gendex/noa/n17.html).
25. An L'₂₄(6¹2¹⁵) (http://designcomputing.net/gendex/noa/n18.html).
26. An L'₂₄(6¹2¹⁵) (http://designcomputing.net/gendex/noa/n18bis.html).
27. An L'₂₄(6¹2¹⁸) (http://designcomputing.net/gendex/noa/n19.html).
28. An L'₂₄(2¹3¹¹) (http://designcomputing.net/gendex/noa/n20.html).
29. An L'₂₄(3¹4⁷) (http://designcomputing.net/gendex/noa/n21.html).
30. An L'₂₄(4⁴2⁴) (http://designcomputing.net/gendex/noa/n22.html).
31. An L'₈₄(2⁸6¹14¹3²) (http://designcomputing.net/gendex/noa/n23.html).
32. An L'₁₀₀(10⁴2⁴3²) (http://designcomputing.net/gendex/noa/n24.html).
33. An S₁₆(2¹⁵) (http://designcomputing.net/gendex/noa/s1.html).
34. An S₁₁(2¹¹) (http://designcomputing.net/gendex/noa/s2.html).
35. An S₈(2¹⁴) (http://designcomputing.net/gendex/noa/s3.html).
36. An S₁₂(2¹⁸) (http://designcomputing.net/gendex/noa/s4.html).
37. An S₁₂(6⁵4⁴) (http://designcomputing.net/gendex/noa/s5.html).
38. An S₂₀(5⁵4¹) (http://designcomputing.net/gendex/noa/s6.html).
39. An S₁₆(2¹⁶8⁸) (http://designcomputing.net/gendex/noa/s7.html).
40. An S₂₀(2¹⁹4¹5⁵) (http://designcomputing.net/gendex/noa/s8.html).

Notes:

• Examples 1-6: mixed level OAs. The new L₆₀(2¹⁵6¹10¹) in the example 6 was obtained by adding sequentially five 2-level columns to the L₆₀(2¹⁰6¹10¹) in the Sloane OA library. The new L₈₄(2¹⁴6¹14¹) in the example 6 was obtained by adding sequentially six 2-level columns to theL₈₄(2⁸6¹14¹) in the Sloane OA library.
• Example 7-32: mixed level near-OAs. Some of these arrays were obtained by adding additional columns to existing OAs. The L'₁₀₀(10⁴2⁴3²) in example 32 was obtained by adding sequentially two 3-level column to the OA L₁₀₀(10⁴2⁴). This new OA was in turn obtained by adding sequentially four 2-level columns to the L₁₀₀(10⁴) in the Sloane OA library. Note that the arrays in examples 7-29 correspond to those in Table 2 of Ma et. al. (2000) and Table 4 of Xu (2002). Examples 15 and 16 provide two solutions to the L'₁₂(3²2⁷). In the second solution (example 16), the first two 3-level columns are orthogonal to the remaining columns. Also, examples 25 and 26 provides two solutions to the L'₂₄(6¹2¹⁵). The average criterion was used to obtained the first solution (example 25) and the minimax criterion was used to obtain the second solution (example 26).
• Example 32-37: 2-level saturated and supersaturated designs.
• Example 38-40: mixed level supersaturated designs. The designs in the last three examples were constructed in the same way as those in Table 2 of Koukouvinos & Mantas (2005), i.e. by adding additional columns to the L₁₆(2¹⁵) and L₂₀(2¹⁹) respectively.

References

Booth, K.H.V. & Cox, D.R. (1962) Some systematic supersaturated designs. Technometrics 4, 489-495.
Cheng, C.S. (1997) E(s²)-optimal supersaturated designs. Statistica Sinica 7, 929-939.
Fang, K-T. , Lin, D. K. J. & Liu, M-Q. (2003) Optimal mixed-level supersaturated design. Metrika 58, 279-291.
Fang, K-T., Ge, G., Liu, M-Q., Qin, H. (2004) Combinatorial constructions for optimal supersaturated designs. Discrete Mathematics 279, 191-202.
Hedayat, A. S., Sloane, N. J. A. & Stufken J. (1999) Orthogonal arrays: Theory and Applications, New York:Springer-Verlag.
Koukouvinos, C. & Mantas, P. (2005) Construction of some E(f_NOD) optimal mixed-level supersaturated designs. Statistics & Probability Letters 74, 312-321.
Kuhfeld, W. F. & Tobias, R. D. (2005) Large factorial designs for product engineering and market research applications. Technometrics 47, 122-132.
Lin, D.K.J. (1993) A new class of supersaturated designs. Technometrics 35, 28-31.
Lu, X., Hu, W. & Zheng, Y. (2003) A systematical procedure in the construction of multi-level supersaturated designs. J. of Statistical Planning & Inference 115, 287-310.
Ma, C-X., Fang, K-T & Liski, E. (2000) A new approach in constructing orthogonal and nearly orthogonal arrays. Metrika 50, 255-268.
Nguyen, N-K. (1996a) An algorithmic approach to constructing supersaturated designs. Technometrics 38, 205-209.
Nguyen, N-K. (1996b) A note on the construction of near-orthogonal arrays with mixed levels and economic run size. Technometrics 38, 279-283.
Nguyen, N-K & Liu, M-Q. (2008) Orthogonal and near-orthogonal arrays constructed from incomplete block designs. To appear in Computational Statistics & Data Analysis.
Rao, C. R. (1947) Fractional experiments derivable from combinatorial arrangements of arrays. J. of the Statistical Society (Supp.) 9, 128-139.
Taguchi, G. (1959) Linear graphs for orthogonal arrays and their applications to experimental designs, with the aid of various techniques. Report of Statistical Applications Research, Japanese Union of Scientists and Engineers 6, 1-43.
Tang, B. & Wu, C.F.J. (1997) A method for constructing supersaturated designs and its E(s²)-property. Canadian J. of Statistics 25, 191-201
Wang, J.C. & Wu, C.F.J. (1992) Nearly orthogonal arrays with mixed levels and small runs. Technometrics 34, 409-422.
Wu, C.F.J & M. Hamada (2000) Experiments: Planning, Analysis and Parameter Design Optimization. New York: Wiley.
Xu, H. (2002) An algorithm for constructing orthogonal and nearly-orthogonal arrays with mixed levels and small runs. Technometrics 44, 356-368.

©2008 Design Computing