Skip to main content
School of Physical Sciences School of Physical Sciences
  1. HOME
  2. News & Events
  3. articles
  4. 2022
  5. The Science of…Linear Algebra and the Design Matrix

The Science of…Linear Algebra and the Design Matrix

December 14, 2022 | By Michelle Franklin

Johannes Brust is a visiting scholar with the Department of Mathematics. Earlier this year he published a feature article in Image, the Bulletin of the International Linear Algebra Society that discusses matrix designs for COVID-19 group testing. In this edition of “The Science of…” he talks about his paper and his work in linear algebra.

 

brust-johannes.jpgQ: Tell us about the field of mathematics you study.

Johannes Brust: My background is in applied math and my research focus is on the development of algorithms (methods) in optimization and numerical linear algebra. When I was an undergraduate, I wanted to work in economics or finance, but I found myself wanting more challenging problems, so I decided to do a graduate degree in applied math. Broadly, it’s numerical analysis — computations to make processes more efficient. The specific topics I study are numerical linear algebra (finding a structure for multiple equations and then using the structure to improve accuracy or efficiency) and numerical optimization (finding parameters to make a model fit to data better or streamlining a process in an automatic way).

 

Q: Can you explain numerical optimization more — what do you mean by making a model fit to data better?

JB: I can give you a financial example. Imagine you have a model of prices in the options market that would behave in a certain way in an ideal world — certain relations would result in a certain price and the relations are governed by a set of inputs or parameters. As the market evolves, the parameters may change, or you might need a different set of parameters. If there are a lot of changing parameters, to make the model fit to the observed prices, you would need a method to minimize the difference between the data points and the computer price model —that is the fitting of the data.

Essentially, you are trying to find relationships between different characteristics and then find a trend that allows us to make predictions. That could be anything from the stock market to population growth charts, which you might see in a doctor’s office.

 

Q: Your feature article in Image discusses matrix designs for COVID-19 group testing. Can you walk us through it?

JB: In populations where the prevalence of COVID is low, I wondered if there was a way to conserve resources through group testing or pooling. Is it possible to use a systematic approach to improve on methods that had been developed beforehand? If you are able to identify a certain number of positive cases precisely with a single design, then it could be straightforward to use. You could make a template available to a lab that follows the pattern of the matrix in terms of assigning samples to a test.

 

Q: How do you design a matrix?

JB: This was based on arranging samples in a grid format and then using that format to group points in a grid to define a test of samples. Partly I wanted to see if certain things would repeat themselves, if there were any patterns. If samples are aligned in a grid, can they be combined in a group, can we combine other samples in another group? Can we identify properties where if those properties are satisfied by the groups, we could exactly decode the information that was put into the matrix when we are trying to find out which samples are positive? If we can achieve something that reproduces the properties, then we can obtain the method that will be able to do the pooling tests.

illustration of affine and projective planes
Multipool matrices can be constructed using an affine plane (l). A projective plane (r) can be derived from an affine plane.

 

Q: Where does linear algebra come in?

JB: To do this work relatively fast, we used linear relations — arranging samples into squares. Later, we looked at direct angles and drawing lines into the arrangement of the samples, but everything is discrete, so the lines wrap around the square and start over again. You have to make sure none of the lines intersect because that would correspond to cases where one of the properties is not satisfied anymore. We looked for parallel lines so all samples are covered, but each line would then define a new test. Then we needed to find a formula that can be used to compute each of the indices that would then map into one of the samples.

 

Q: How do you get a pool sample without testing samples individually?

JB: Let’s say you have a set of vials with samples in them, but you don’t know if the samples are positive or negative for COVID. You can take an additional vial and mix all of those samples together and then test that one group sample. If the group sample is negative, we can conclude all the original ones are negative too. If it’s positive, either we did the grouping in such a way that we can infer from the set of groups, which ones of the original samples had to be positive because we recorded how we added them together. Or in a two-step case, we would go back and test them individually. 

 

Q: Is this practical? Is this something labs would implement?

JB: There are programs where these types of strategies can be used to gain an overview of how the disease is developing or evolving. When you have a large sample size, this can act like a screening testing to roughly determine what the percentage of positive cases might be. 

 

Q: Are these matrices already being used for testing?

JB: We wanted to generate a matrix that can serve as a template to guide which sample goes into which test. We have already launched software where you can set the parameters (e.g., how large the pool should be, how many positives are expected) to create a matrix that shows which sample to add to which test. The software is public domain, with different versions in different languages (a computing language and an open-source language that doesn't require any commercial software to use). The PP software (polynomial pools) is already being used in bioinformatics and genome sequencing, which uses similar testing strategies.

Ultimately, we hope that students will use the software and become enthusiastic about continuing the work. I’m sure there are many ways to improve the software and make it more practical and efficient. We are open to collaborations!

 

For More Information