A researcher needs to solve for the same matrix and different right-hand sides

PHYSICS · Multi-part · Fermi University Physics · Mathematical Methods for Physics · Numerical and computational mathematics · Numerical and computational mathematics

Error, Chance and the Machine, Ch Linear systems, least squares and the singular value decomposition

Problem

A researcher needs to solve Ax=bk\mathsf{A}\mathbf{x} = \mathbf{b}_k for the same n×nn\times n matrix A\mathsf{A} and 5050 different right-hand sides b1,…,b50\mathbf{b}_1, \ldots, \mathbf{b}_{50}. They write: 'I will compute A−1\mathsf{A}^{-1} once, at a cost of about 2n32n^3 flops, and then get each solution from xk=A−1bk\mathbf{x}_k = \mathsf{A}^{-1}\mathbf{b}_k at a cost of 2n22n^2 flops each. This is both the cheapest and the most accurate way to handle many right-hand sides, since I only factorise once.' ((a)) Find the error in this reasoning, addressing both the cost claim and the accuracy claim, and compare with the strategy of computing the LU factorisation of A\mathsf{A} once and re-using it for each right-hand side. ((b)) For n=3000n = 3000, estimate the flop count of each strategy (factorisation plus 50 solves) and state which is cheaper. ((c)) Show that no number of right-hand sides makes the explicit inverse the cheaper strategy.

Browse the problem library