Reformulating the problem<\/strong><\/h4>\nWe start by re-writing the problem we want to solve. Instead of applying our matrix multiplications with A<\/strong> sequentially (one-after the other), we re-write our problem as a bigger system with more structure<\/p>\n![\"\"](\"https:\/\/research.reading.ac.uk\/met-darc\/wp-content\/uploads\/sites\/48\/2025\/06\/Picture1.png\")
<\/p>\n
This means that it is more straightforward to split multiplications across different processors, hopefully reducing our overall time to obtain the solution.<\/p>\n
Preconditioning<\/strong><\/h4>\nThe challenge is now to accelerate the solution of this larger problem. Preconditioners<\/em> allow us to solve an equivalent problem, with a better mathematical structure which means that we should see more improvement to our answer with each step. We can think of this like going from the third floor to the first floor, and replacing 2 very shallow steps with one deeper step on the staircase \u2013 at each step we take, we will get closer to our goal, but it may take us more effort to make those steps<\/p>\nFor problems of the form shown above, there are well-known preconditioners that help accelerate convergence. However, one of the components of the standard approach is too expensive for the problem we are interested in. For our staircase analogy, this is like saying our original method was to take one step from the third floor to the second floor \u2013 which is definitely too much effort!<\/p>\n
Adding another solver<\/strong><\/h4>\nOur idea is to replace the expensive step, with another iterative method.\u00a0 Another iterative method will add a new staircase between our floors, making each step a bit easier, but adding more steps (which could increase the overall time). We have to solve k<\/em> of these sub-problems, and we want to solve them approximately \u2013 maybe our staircase doesn\u2019t need to go all the way to the second floor to be useful.<\/p>\nThe main mathematical work of Tabeart et al. (2025) was to understand whether these sub-problems make staircases that definitely take us to the next floor, and how quickly the stairs will take us there. Two of the k<\/em> sub-problems fit into existing theory, which tells us that we do reach the next floor, with one problem getting there much more slowly. The other k-2<\/em> \u00a0stairs were more problematic \u2013 we saw numerically that our method worked, but guaranteeing it mathematically needed some technical mathematical proofs. We discovered out that all of our stairs are guaranteed to reach the next floor, and developed an easy-to-compute upper bound on how long it will take us to get there.<\/p>\nMaking a practical algorithm<\/strong><\/h4>\nWe can also use these new bounds to reduce the total number of iterations\u00a0. By using information about how quickly each method descends, we can solve each of our problems to the same tolerance (build our staircases to the same height). When we have a limited computational budget, this means we are not wasting resources building one intermediate staircase much further than the others.<\/p>\n
![\"\"](\"https:\/\/research.reading.ac.uk\/met-darc\/wp-content\/uploads\/sites\/48\/2025\/06\/1750240001441-a48ebc38-8db8-4081-86fc-d4ec29199316_1.png\")
<\/p>\n
This figure shows the performance of our new method against solving the original problem with no preconditioner. The top panels show the number of iterations (steps) to find an acceptable solution, and the bottom panels show how much effort it cost us to get there. The left and right panels show two different versions of the preconditioner. The black line shows the computational effort to solve the original problem, the blue line the method with the new iterative <\/em>preconditioner where we allocate the same budget to each sub-problem. Finally the red line shows the new iterative preconditioner where we use the mathematical theory to help us solve each problem to about the same tolerance (build the stairs to the same height). Both our new methods do much better than solving the problem with no preconditioner, for iterations and computational cost. Our second method is easy to apply, and results in even better performance than our first method. We started off with a problem where we couldn\u2019t use the existing approach due to computational limitations. These limitations introduced us to some new mathematics and a new algorithm!<\/p>\n
<\/p>\n
This means that it is more straightforward to split multiplications across different processors, hopefully reducing our overall time to obtain the solution.<\/p>\n
Preconditioning<\/strong><\/h4>\nThe challenge is now to accelerate the solution of this larger problem. Preconditioners<\/em> allow us to solve an equivalent problem, with a better mathematical structure which means that we should see more improvement to our answer with each step. We can think of this like going from the third floor to the first floor, and replacing 2 very shallow steps with one deeper step on the staircase \u2013 at each step we take, we will get closer to our goal, but it may take us more effort to make those steps<\/p>\nFor problems of the form shown above, there are well-known preconditioners that help accelerate convergence. However, one of the components of the standard approach is too expensive for the problem we are interested in. For our staircase analogy, this is like saying our original method was to take one step from the third floor to the second floor \u2013 which is definitely too much effort!<\/p>\n
Adding another solver<\/strong><\/h4>\nOur idea is to replace the expensive step, with another iterative method.\u00a0 Another iterative method will add a new staircase between our floors, making each step a bit easier, but adding more steps (which could increase the overall time). We have to solve k<\/em> of these sub-problems, and we want to solve them approximately \u2013 maybe our staircase doesn\u2019t need to go all the way to the second floor to be useful.<\/p>\nThe main mathematical work of Tabeart et al. (2025) was to understand whether these sub-problems make staircases that definitely take us to the next floor, and how quickly the stairs will take us there. Two of the k<\/em> sub-problems fit into existing theory, which tells us that we do reach the next floor, with one problem getting there much more slowly. The other k-2<\/em> \u00a0stairs were more problematic \u2013 we saw numerically that our method worked, but guaranteeing it mathematically needed some technical mathematical proofs. We discovered out that all of our stairs are guaranteed to reach the next floor, and developed an easy-to-compute upper bound on how long it will take us to get there.<\/p>\nMaking a practical algorithm<\/strong><\/h4>\nWe can also use these new bounds to reduce the total number of iterations\u00a0. By using information about how quickly each method descends, we can solve each of our problems to the same tolerance (build our staircases to the same height). When we have a limited computational budget, this means we are not wasting resources building one intermediate staircase much further than the others.<\/p>\n
<\/p>\n
This figure shows the performance of our new method against solving the original problem with no preconditioner. The top panels show the number of iterations (steps) to find an acceptable solution, and the bottom panels show how much effort it cost us to get there. The left and right panels show two different versions of the preconditioner. The black line shows the computational effort to solve the original problem, the blue line the method with the new iterative <\/em>preconditioner where we allocate the same budget to each sub-problem. Finally the red line shows the new iterative preconditioner where we use the mathematical theory to help us solve each problem to about the same tolerance (build the stairs to the same height). Both our new methods do much better than solving the problem with no preconditioner, for iterations and computational cost. Our second method is easy to apply, and results in even better performance than our first method. We started off with a problem where we couldn\u2019t use the existing approach due to computational limitations. These limitations introduced us to some new mathematics and a new algorithm!<\/p>\n
For problems of the form shown above, there are well-known preconditioners that help accelerate convergence. However, one of the components of the standard approach is too expensive for the problem we are interested in. For our staircase analogy, this is like saying our original method was to take one step from the third floor to the second floor \u2013 which is definitely too much effort!<\/p>\n
Adding another solver<\/strong><\/h4>\nOur idea is to replace the expensive step, with another iterative method.\u00a0 Another iterative method will add a new staircase between our floors, making each step a bit easier, but adding more steps (which could increase the overall time). We have to solve k<\/em> of these sub-problems, and we want to solve them approximately \u2013 maybe our staircase doesn\u2019t need to go all the way to the second floor to be useful.<\/p>\nThe main mathematical work of Tabeart et al. (2025) was to understand whether these sub-problems make staircases that definitely take us to the next floor, and how quickly the stairs will take us there. Two of the k<\/em> sub-problems fit into existing theory, which tells us that we do reach the next floor, with one problem getting there much more slowly. The other k-2<\/em> \u00a0stairs were more problematic \u2013 we saw numerically that our method worked, but guaranteeing it mathematically needed some technical mathematical proofs. We discovered out that all of our stairs are guaranteed to reach the next floor, and developed an easy-to-compute upper bound on how long it will take us to get there.<\/p>\nMaking a practical algorithm<\/strong><\/h4>\nWe can also use these new bounds to reduce the total number of iterations\u00a0. By using information about how quickly each method descends, we can solve each of our problems to the same tolerance (build our staircases to the same height). When we have a limited computational budget, this means we are not wasting resources building one intermediate staircase much further than the others.<\/p>\n
<\/p>\n
This figure shows the performance of our new method against solving the original problem with no preconditioner. The top panels show the number of iterations (steps) to find an acceptable solution, and the bottom panels show how much effort it cost us to get there. The left and right panels show two different versions of the preconditioner. The black line shows the computational effort to solve the original problem, the blue line the method with the new iterative <\/em>preconditioner where we allocate the same budget to each sub-problem. Finally the red line shows the new iterative preconditioner where we use the mathematical theory to help us solve each problem to about the same tolerance (build the stairs to the same height). Both our new methods do much better than solving the problem with no preconditioner, for iterations and computational cost. Our second method is easy to apply, and results in even better performance than our first method. We started off with a problem where we couldn\u2019t use the existing approach due to computational limitations. These limitations introduced us to some new mathematics and a new algorithm!<\/p>\n
The main mathematical work of Tabeart et al. (2025) was to understand whether these sub-problems make staircases that definitely take us to the next floor, and how quickly the stairs will take us there. Two of the k<\/em> sub-problems fit into existing theory, which tells us that we do reach the next floor, with one problem getting there much more slowly. The other k-2<\/em> \u00a0stairs were more problematic \u2013 we saw numerically that our method worked, but guaranteeing it mathematically needed some technical mathematical proofs. We discovered out that all of our stairs are guaranteed to reach the next floor, and developed an easy-to-compute upper bound on how long it will take us to get there.<\/p>\n We can also use these new bounds to reduce the total number of iterations\u00a0. By using information about how quickly each method descends, we can solve each of our problems to the same tolerance (build our staircases to the same height). When we have a limited computational budget, this means we are not wasting resources building one intermediate staircase much further than the others.<\/p>\n This figure shows the performance of our new method against solving the original problem with no preconditioner. The top panels show the number of iterations (steps) to find an acceptable solution, and the bottom panels show how much effort it cost us to get there. The left and right panels show two different versions of the preconditioner. The black line shows the computational effort to solve the original problem, the blue line the method with the new iterative <\/em>preconditioner where we allocate the same budget to each sub-problem. Finally the red line shows the new iterative preconditioner where we use the mathematical theory to help us solve each problem to about the same tolerance (build the stairs to the same height). Both our new methods do much better than solving the problem with no preconditioner, for iterations and computational cost. Our second method is easy to apply, and results in even better performance than our first method. We started off with a problem where we couldn\u2019t use the existing approach due to computational limitations. These limitations introduced us to some new mathematics and a new algorithm!<\/p>\nMaking a practical algorithm<\/strong><\/h4>\n
<\/p>\n