| Title: | 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. Implements and generalises the method of Boudraa, Gheribi-Aoulmi and Laib (2013, International Journal of Research and Reviews in Applied Sciences, 17(2), 167-176), which was previously available only for p = 2, and the uniform design constructions of Fang et al. (2004) <doi:10.1016/S0012-365X(03)00100-6>. Designs of every recursion stage can be extracted, and all constructions are validated against the parameters published in the original paper. |
| Authors: | Mohamed Laib [aut, cre], Abla Boudraa [aut], Zebida Gheribi-Aoulmi [aut] |
| Maintainer: | Mohamed Laib <laib.med@gmail.com> |
| License: | GPL-3 |
| Version: | 2.0.1 |
| Built: | 2026-09-26 09:57:03 UTC |
| Source: | https://github.com/mlaib/pgm2 |
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.
BIB(m, p = 2)BIB(m, p = 2)
m |
Dimension of the projective geometry (an integer, |
p |
Order of the Galois field GF(p); must be prime. Defaults to
|
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).
A list with components:
VNumber of treatments, .
BNumber of blocks (equal to V: the design is
symmetric).
RReplication of each treatment, .
KBlock size (equal to R).
LambdaConcurrence parameter, .
BIBThe design: a B x K matrix whose rows
are the blocks, containing treatment labels.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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$BIBX <- 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
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.
Gen(n, mat)Gen(n, mat)
n |
Index of the block (sub-variety) to be deleted; an integer
between 1 and |
mat |
The matrix of the BIBD (rows are blocks), e.g. the |
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.
A list with components:
VNumber of treatments of the new BIBD.
BNumber of blocks.
RReplication of each treatment.
KSize of each block.
BIB2The design: a matrix whose rows are the blocks.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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$KX <- 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
Builds the reduced resolvable design of Boudraa et al.
(2013) directly, together with its associated uniform design
: the treatments are the points
of the affine geometry AG(m, p), each factor corresponds to one
-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.
Qn(m, n, p = 2)Qn(m, n, p = 2)
m |
Dimension of the projective geometry (an integer, |
n |
Stage of the recursion, an integer with |
p |
Order of the Galois field GF(p); must be prime. Defaults to
|
The number of factors is the Gaussian binomial coefficient
. Any two distinct runs coincide in exactly
factors (the number of -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
then the level partition induced by W is a
coarsening of the one induced by W'.
For the design is the saturated Rao-Hamming orthogonal
array . For ,
recoding its two levels to gives the Sylvester-Hadamard
member of the Plackett-Burman class of order , up to row,
column and level equivalence.
Subspaces are enumerated by canonical reduced row echelon form, which
generates each subspace exactly once rather than scanning subsets of
the nonzero vectors. Labelling then visits, for every
subspace and every run, the elements of a coset, so the
cost is approximately
plus
factor-construction overhead, with output size
. This is why stages
with similar factor counts can differ in runtime. On the machine used
for the package benchmarks, Qn(5, 2) completed in well under a
second, Qn(7, 1) in a few seconds and Qn(7, 3) (11811
factors) in a few minutes; timings are hardware dependent.
A list with components:
VNumber of treatments (runs), .
BNumber of blocks of .
RReplication of each treatment (= number of factors).
KBlock size, .
LambdaConcurrence parameter (constant, see Details).
LevelsNumber of levels of each factor, .
UDThe uniform design: a matrix of
levels 1..Levels.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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 runsQ <- 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
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)).
Resolvable(n, mat)Resolvable(n, mat)
n |
Index of the block (sub-variety) to be deleted; an integer
between 1 and |
mat |
The matrix of the BIBD (rows are blocks), e.g. the |
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.
A list with components:
VNumber of treatments of the RBIBD, .
BNumber of blocks.
RReplication of each treatment.
KSize of each block, .
RBIBThe design: a matrix whose rows are the blocks.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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$RBIBX <- 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
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.
Steps(m, n, stage = "all", p = 2)Steps(m, n, stage = "all", p = 2)
m |
Dimension of the projective geometry (an integer, |
n |
Index of the block (sub-variety) to be deleted at each stage.
The same index is used at every stage, and the number of blocks shrinks
along the recursion, so |
stage |
Stages wanted, a character vector (default
|
p |
Order of the Galois field GF(p); must be prime. Defaults to
|
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).
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.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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)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)
Builds a symmetric uniform design (UD) from a resolvable balanced incomplete block design, following the correspondence of Fang et al.: the blocks are partitioned into parallel classes, each class becomes a factor (column), and the level of a treatment on a factor is the index of the block of that class containing it.
Uniform(mat)Uniform(mat)
mat |
The matrix of the RBIBD (rows are blocks), e.g. the
|
The resolution is found by exact-cover search with
backtracking, so the result does not depend on the order of the rows of
mat: any row permutation yields the same design up to a
permutation of the factors and a relabelling of levels. Earlier
versions used a first-fit greedy extraction, which could fail on a
valid resolvable design presented in an unfavourable row order.
If mat admits no resolution, or the search budget is exhausted,
an informative error is raised rather than a partial design returned.
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 runs and p
levels per factor.
A list with components:
nNumber of experiments (runs) of the uniform design.
FNumber of factors (one per parallel class).
UDThe design: an n x F matrix of levels.
classesA list giving, for each factor, the row indices
of mat forming that parallel class.
Mohamed Laib, Abla Boudraa and Zebida Gheribi-Aoulmi
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.
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) # the result does not depend on the order of the blocks set.seed(1) P <- Y$RBIB[sample(nrow(Y$RBIB)), ] dim(Uniform(P)$UD)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) # the result does not depend on the order of the blocks set.seed(1) P <- Y$RBIB[sample(nrow(Y$RBIB)), ] dim(Uniform(P)$UD)