Package {PGM2}

PGM2: Recursive Construction of Nested Resolvable Designs and Associated Uniform Designs over GF(p)

Description

Recursive construction of balanced incomplete block designs (BIBDs), their successive generations, resolvable BIBDs (RBIBDs) and associated uniform designs (UDs), derived from finite projective geometries PG(m, p) over a Galois field GF(p) of any prime order p.

Version 2.0 generalises the whole package from GF(2) to GF(p) for any prime p, as described in the underlying paper (Boudraa et al., 2013), whose theory is stated for general p even though versions <= 1.2 of the package implemented only p = 2.

Author(s)

Maintainer: Mohamed Laib laib.med@gmail.com

Authors:

• Mohamed Laib laib.med@gmail.com

• Abla Boudraa

• Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

D. Dugue (1958). Traite de statistique theorique et appliquee. Masson et Cie, Paris.

Z. Gheribi-Aoulmi and M. Bousseboua (2005). Recursive methods for construction of balanced n-ary block designs. Serdica Mathematical Journal, 31, 189–200.

K.T. Fang, X. Lu, Y. Tang and J. Yin (2004). Constructions of uniform designs by using resolvable packings and coverings. Discrete Mathematics, 274, 25–40.

K.T. Fang, G.N. Ge, M.Q. Liu and H. Qin (2004). Construction of uniform designs via super-simple resolvable t-designs. Utilitas Mathematica, 66, 15–32.

See Also

Useful links:

• https://mlaib.net

• https://github.com/mlaib/PGM2

• Report bugs at https://github.com/mlaib/PGM2/issues

Examples

# The chain of designs of PG(3, 2):
X <- BIB(3)                  # BIBD (15, 7, 3)
Y <- Resolvable(1, X$BIB)    # RBIBD (8, 14, 7, 4, 3)
Uniform(Y$RBIB)$UD           # U(8, 2^7)

# The same chain over GF(3):
X3 <- BIB(2, p = 3)          # BIBD (13, 4, 1)
Y3 <- Resolvable(1, X3$BIB)  # RBIBD (9, 12, 4, 3, 1)
Uniform(Y3$RBIB)$UD          # U(9, 3^4)

Balanced Incomplete Block Design from PG(m, p)

Description

Builds the symmetric balanced incomplete block design (BIBD) whose treatments are the points of the projective geometry PG(m, p) over the Galois field GF(p) and whose blocks are its hyperplanes.

Usage

BIB(m, p = 2)

Arguments

Details

Treatments are numbered by enumerating the canonical representatives of the projective points in base-p counting order. Block i consists of the points x lying on the hyperplane a_i . x = 0 (mod p), where a_i is the i-th point (point-hyperplane duality).

Value

A list with components:

V

Number of treatments, (p^{m+1}-1)/(p-1).

B

Number of blocks (equal to V: the design is symmetric).

R

Replication of each treatment, (p^m-1)/(p-1).

K

Block size (equal to R).

Lambda

Concurrence parameter, (p^{m-1}-1)/(p-1).

BIB

The design: a B x K matrix whose rows are the blocks, containing treatment labels.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

D. Dugue (1958). Traite de statistique theorique et appliquee. Masson et Cie, Paris.

Examples

X <- BIB(4)        # BIBD (31, 15, 7) from PG(4, 2)
X$V; X$K; X$Lambda

Y <- BIB(2, p = 3) # BIBD (13, 4, 1): the projective plane of order 3
Y$BIB

BIBD of the Next Generation

Description

Extracts the balanced incomplete block design of the next generation by deleting block n of a BIBD built from a projective geometry: each remaining block is intersected with the deleted one, so the deleted block plays the role of a lower-dimensional projective geometry and the intersections are its hyperplanes.

Usage

Gen(n, mat)

Arguments

Details

Works for any order p: block sizes are derived from the data instead of the binary-only formula used in PGM2 <= 1.2 (for a symmetric BIBD every remaining block meets the deleted block in exactly Lambda treatments). For a BIBD from PG(m, p), the result is the BIBD of PG(m - 1, p) on the treatments of the deleted block.

Value

A list with components:

V

Number of treatments of the new BIBD.

B

Number of blocks.

R

Replication of each treatment.

K

Size of each block.

BIB2

The design: a matrix whose rows are the blocks.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

Examples

X <- BIB(4)              # BIBD (31, 15, 7) from PG(4, 2)
X2 <- Gen(1, X$BIB)      # second generation: BIBD (15, 7, 3)
X2$V; X2$K

Y <- BIB(3, p = 3)       # BIBD (40, 13, 4) from PG(3, 3)
Y2 <- Gen(1, Y$BIB)      # second generation: BIBD (13, 4, 1)
Y2$V; Y2$K

Reduced Resolvable Design of Stage n and its Uniform Design

Description

Builds the reduced resolvable design Q^*_n of Boudraa et al. (2013) directly, together with its associated uniform design U(p^m, (p^n)^{r^{**}_n}): the treatments are the p^m points of the affine geometry AG(m, p), each factor corresponds to one (m-n)-dimensional linear subspace W of GF(p)^m (one parallel class of affine flats), and the level of a treatment x on factor W is the coset x + W.

Usage

Qn(m, n, p = 2)

Arguments

Details

The number of factors is the Gaussian binomial coefficient \binom{m}{m-n}_p. Any two distinct runs coincide in exactly \binom{m-1}{m-n-1}_p factors (the number of (m-n)-dimensional subspaces containing a fixed nonzero vector), so the design is equidistant; consequently it attains the discrete-discrepancy lower bound of Fang et al. (2004). Across stages the levels refine: if W' \subset W then the level partition induced by W is a coarsening of the one induced by W'.

For n = 1 the design is the Rao-Hamming orthogonal array OA(p^m, (p^m-1)/(p-1), p, 2); for p = 2, n = 1 the Plackett-Burman design of order 2^m.

Subspaces are enumerated by canonical reduced row echelon form, so the cost is proportional to the number of factors (the Gaussian binomial coefficient) times the p^m runs, rather than to the number of subsets of points. Every design with p^m \le 128 is reachable; as a guide, Qn(5, 2) takes well under a second, Qn(7, 1) a few seconds and Qn(7, 3) (11811 factors) a few minutes.

Value

A list with components:

V

Number of treatments (runs), p^m.

B

Number of blocks of Q^*_n.

R

Replication of each treatment (= number of factors).

K

Block size, p^{m-n}.

Lambda

Concurrence parameter (constant, see Details).

Levels

Number of levels of each factor, p^n.

UD

The uniform design: a p^m \times R matrix of levels 1..Levels.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

K.T. Fang, X. Lu, Y. Tang and J. Yin (2004). Constructions of uniform designs by using resolvable packings and coverings. Discrete Mathematics, 274, 25–40.

Examples

Q <- Qn(3, 1)            # stage 1 of PG(3,2): U(8, 2^7), Plackett-Burman
Q$UD

Q2 <- Qn(3, 2)           # stage 2: U(8, (2^2)^7), Example 3 of the paper
Q32 <- Qn(3, 1, p = 3)   # U(27, 3^13)
c(Q32$V, Q32$B, Q32$R, Q32$K, Q32$Lambda)

Qn(4, 2)$R               # 35 four-level factors on 16 runs

Resolvable Balanced Incomplete Block Design

Description

Extracts the resolvable balanced incomplete block design (RBIBD) residual to block n of a BIBD constructed from a projective geometry: block n is deleted together with all its treatments, and the surviving parts of the remaining blocks form a resolvable design (for a BIBD from PG(m, p) this is the design of the affine geometry AG(m, p)).

Usage

Resolvable(n, mat)

Arguments

Details

Works for any order p: residual block sizes are derived from the data instead of the binary-only formula used in PGM2 <= 1.2 (every remaining block loses exactly Lambda treatments to the deleted block, so all residual blocks have size K - Lambda). The blocks partition into R parallel classes of p blocks each.

Value

A list with components:

V

Number of treatments of the RBIBD, p^m.

B

Number of blocks.

R

Replication of each treatment.

K

Size of each block, p^{m-1}.

RBIB

The design: a matrix whose rows are the blocks.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

R.C. Bose (1942). A note on the resolvability of balanced incomplete block designs. Sankhya, 6, 105–110.

Examples

X <- BIB(4)                    # BIBD (31, 15, 7) from PG(4, 2)
Y <- Resolvable(1, X$BIB)      # RBIBD (16, 30, 15, 8, 7)
Y$V; Y$B; Y$K

Z <- BIB(2, p = 3)             # BIBD (13, 4, 1) from PG(2, 3)
W <- Resolvable(1, Z$BIB)      # RBIBD (9, 12, 4, 3, 1): AG(2, 3)
W$RBIB

All Stages of the Recursive Construction

Description

Runs the whole recursion of Boudraa et al. (2013) starting from the projective geometry PG(m, p): at each stage the current BIBD yields a resolvable design (via Resolvable) and its associated uniform design (via Uniform), and the next-generation BIBD is extracted (via Gen) until the geometry is exhausted.

Usage

Steps(m, n, stage = "all", p = 2)

Arguments

Value

A named list with (depending on stage) components BIB1 (the first-generation BIBD as returned by BIB), BIBg (a list of the next-generation BIBDs), Resolvables (a list of the resolvable designs of every stage) and UDs (a list of the associated uniform designs).

Note

The return structure is tidier than in PGM2 <= 1.2, where the stages were spliced into one flat, partially unnamed list: each stage is now a proper sub-list.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

A. Boudraa, Z. Gheribi-Aoulmi and M. Laib (2013). Recursive method for construction of resolvable nested designs and uniform designs associated. International Journal of Research and Reviews in Applied Sciences, 17(2), 167–176.

Z. Gheribi-Aoulmi and M. Bousseboua (2005). Recursive methods for construction of balanced n-ary block designs. Serdica Mathematical Journal, 31, 189–200.

Examples

s <- Steps(3, 1)               # all stages of PG(3, 2)
names(s)
s$UDs[[1]]$UD                  # U(8, 2^7)

s3 <- Steps(3, 1, p = 3)       # all stages of PG(3, 3)
s3$UDs[[1]]$UD                 # U(27, 3^13)

Steps(4, 1, c('S1', 'S4'))     # first and last stage only, PG(4, 2)

Uniform Design from a Resolvable BIBD

Description

Builds a symmetric uniform design (UD) from a resolvable balanced incomplete block design, following the correspondence of Fang et al.: the blocks are partitioned greedily into parallel classes, each class becomes a factor (column), and the level of a treatment on a factor is the index of the block containing it within that class.

Usage

Uniform(mat)

Arguments

Details

Works for any order p (the parallel-class extraction is purely combinatorial). For the RBIBD residual to a block of the BIBD of PG(m, p), the result is a uniform design with p^m runs and p levels per factor.

Value

A list with components:

n

Number of experiments (runs) of the uniform design.

F

Number of factors (one per parallel class).

UD

The design: an n x F matrix of levels.

Author(s)

Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi

References

K.T. Fang, X. Lu, Y. Tang and J. Yin (2004). Constructions of uniform designs by using resolvable packings and coverings. Discrete Mathematics, 274, 25–40.

K.T. Fang, G.N. Ge, M.Q. Liu and H. Qin (2004). Construction of uniform designs via super-simple resolvable t-designs. Utilitas Mathematica, 66, 15–32.

Examples

X <- BIB(3)                    # BIBD (15, 7, 3) from PG(3, 2)
Y <- Resolvable(1, X$BIB)      # RBIBD (8, 14, 7, 4, 3)
Uniform(Y$RBIB)$UD             # U(8, 2^7)

Z <- BIB(2, p = 3)             # BIBD (13, 4, 1) from PG(2, 3)
W <- Resolvable(1, Z$BIB)      # RBIBD (9, 12, 4, 3, 1)
Uniform(W$RBIB)$UD             # U(9, 3^4)

Internal arithmetic helpers for GF(p), p prime

Description

Small utilities used by the design constructors: primality check and enumeration of the points of the projective geometry PG(m, p).

Details

Points of PG(m, p) are the nonzero vectors of GF(p)^(m+1) up to multiplication by a nonzero scalar. One canonical representative is kept per point (the one whose first nonzero coordinate equals 1), giving (p^(m+1) - 1)/(p - 1) points. Vectors are enumerated in base-p counting order with the first coordinate as the most significant digit, which for p = 2 reproduces exactly the point (and hence treatment) numbering of PGM2 <= 1.2.