Project DetailsIn tandem with algorithmic and theoretical work, applications in disciplines such as electoral policy and phylogenic reconstruction are a central feature of the project. The student will be able to influence the direction of the project based on her/his interests.
Matrix balancing aims to transform a nonnegative matrix A by a diagonal scaling by matrices D and E so that P = DAE has prescribed row and column sums. Historical motivation for achieving the balance has included interpreting economic data, preconditioning sparse matrices and understanding traffic circulation. More recently, it has been acknowledged that there is a role for matrix balancing in network analysis, inferring phylogenies (via hierarchical clustering) and increasing fairness in elections.
Application of balancing has been limited by a lack of analysis of existing algorithms in order to assess their efficacy for large scale data sets. We have recently filled in some of the holes in this analysis and have had some success in implementing existing and new algorithms on very large problems. The new algorithms we have developed for balancing have been shown to work an order of magnitude faster than the standard algorithm. We would like to develop these algorithms to find implementations suitable for parallel computations on large data sets. And we would like to develop more full the theory of balancing by drawing from the theory of linear programming as well as linear algebra.
SupervisorThe supervisor for this project will be Dr Philip Knight
Further informationFor further information, please contact Dr Knight
Tel: 0141 548 3818