Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Carleton University

$30,000.00

Orthogonal and Covering Arrays

FY 2023-24

Summary
I am interested in the mathematical theory and real world application of finite set systems. I propose research on generalizations of orthogonal arrays which are two-dimensional arrays of symbols with the property that when some small sets of columns are extracted, the resulting rows contain every possible vector with some uniformity. They have applications to numerical methods, software testing, and optimized welding design. Orthogonal arrays (OA) require all small sets of columns and every possible row must appear the same number of times. I am proposing two generalizations, poset OAs where the selection of columns is restricted to the ideals of a partially ordered sets and Lee OAs where all sets of columns are selected but which do not require that all vectors appear. I will study both by understanding the related association schemes which are algebras of matrices with strong combinatorial properties. The duality principle in association schemes shows that OAs can be understood and constructed from error correcting codes. I am particularly interested in codes which meet the Singleton bound as they produce the most efficient orthogonal arrays. Ordered orthogonal arrays, a special type of poset OA have applications to efficient numerical integration and Monte Carlo algorithms. Covering arrays (CA) require all small sets of columns and every vector must appear as a row at least once, but some vectors may appear many times. Their strongest application is reliability testing. I propose to research constructions of CAs from sequences over finite fields and from finite geometries, both building off my previous research. My construction of CAs from sets of "orthogoval" affine planes revealed the existence of conic sets in geometries that have all the combinatorial properties of an algebraically derived family ("pencil") but are not algebraic. I propose to prove that these always exist for geometries over finite fields of even characteristic and relate them to a similar structures known over odd fields. I will generalize orthogoval sets to higher dimensional finite geometries using ovoids, caps and arcs. Motivated by a software testing study which found that the most efficient use of CAs was when the fewest changes are made between test runs, I propose to study the optimally efficient, Single Change Covering Arrays. Finally, industrial welding practices require performing sequences of test welds that correspond to CAs where every row is a permutation. Like poset and Lee OAs, these are governed by association schemes. I propose to generalize standard CA constructions to these specialized cases. I hope to work with computer scientists and engineers who use these combinatorial objects to provide them with the state of the art mathematics and to learn the constraints they face which will lead to new mathematics. I will also explore computational methods and implement these objects and their methods so others can use these tools.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-04668
Name nom
Stevens, Brett
Department département
Mathematics and Statistics
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
30000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2950
Research subject group en
Applied mathematics
Research subject group fr
Applied mathematics
Research subject en
Mathématiques appliquées
Research subject fr
Mathématiques appliquées
Application title
Orthogonal and Covering Arrays
Keyword
association scheme; combinatorial design theory; covering arrays; finite geometry; NRT-metric; orthogonal arrays; permutation arrays; reliability testing; sequences; single change covering arrays
Application summary
I am interested in the mathematical theory and real world application of finite set systems. I propose research on generalizations of orthogonal arrays which are two-dimensional arrays of symbols with the property that when some small sets of columns are extracted, the resulting rows contain every possible vector with some uniformity. They have applications to numerical methods, software testing, and optimized welding design. Orthogonal arrays (OA) require all small sets of columns and every possible row must appear the same number of times. I am proposing two generalizations, poset OAs where the selection of columns is restricted to the ideals of a partially ordered sets and Lee OAs where all sets of columns are selected but which do not require that all vectors appear. I will study both by understanding the related association schemes which are algebras of matrices with strong combinatorial properties. The duality principle in association schemes shows that OAs can be understood and constructed from error correcting codes. I am particularly interested in codes which meet the Singleton bound as they produce the most efficient orthogonal arrays. Ordered orthogonal arrays, a special type of poset OA have applications to efficient numerical integration and Monte Carlo algorithms. Covering arrays (CA) require all small sets of columns and every vector must appear as a row at least once, but some vectors may appear many times. Their strongest application is reliability testing. I propose to research constructions of CAs from sequences over finite fields and from finite geometries, both building off my previous research. My construction of CAs from sets of "orthogoval" affine planes revealed the existence of conic sets in geometries that have all the combinatorial properties of an algebraically derived family ("pencil") but are not algebraic. I propose to prove that these always exist for geometries over finite fields of even characteristic and relate them to a similar structures known over odd fields. I will generalize orthogoval sets to higher dimensional finite geometries using ovoids, caps and arcs. Motivated by a software testing study which found that the most efficient use of CAs was when the fewest changes are made between test runs, I propose to study the optimally efficient, Single Change Covering Arrays. Finally, industrial welding practices require performing sequences of test welds that correspond to CAs where every row is a permutation. Like poset and Lee OAs, these are governed by association schemes. I propose to generalize standard CA constructions to these specialized cases. I hope to work with computer scientists and engineers who use these combinatorial objects to provide them with the state of the art mathematics and to learn the constraints they face which will lead to new mathematics. I will also explore computational methods and implement these objects and their methods so others can use these tools.
Carleton University - $30,000 Grant (2023-24) | Canada Spends