Steps for

Physics $4730,$ Fall $2024$

Homework #$1$

Due Sunday September $8^{th}$

In class we discussed two methods for inverting matrices, that can be generalized to invert a non$-$square matrix. In the singular value decomposition $($SVD$)$ method, we use the fact that any $mn$ matrix A can be broken down as follows:

$A=US{V}^{**}$

where U is an $mm$ unitary matrix, $S$ is an $mn$ positive diagonal matrix, and V is an $nn$ unitary matrix. The inverse of A is given by

$A^{-1}=V{S}^{-1}{U}^{**}$

Another method is the $QR$ decomposition $(QR)$ method. Here, we use the fact that any $mn$ matrix A can be broken down as follows:

$A=QR$

where $Q$ is an $mm$ orthogonal matrix and $R$ is an $mn$ upper triagonal matrix. The inverse of A is given by

$A^{-1}=R^{-1}{Q}^{-1}$

For this assignment, we are going to be doing a benchmark test of the two inversion methods. You should submit a Python script

benchmark.py that does the following:

For $i=1,10$

generate a random $2^i{2}^i$ matrix

find inversion time $t_{SVD}$ via the SVD method

find inversion time $t_{QR}$ via the $QR$ method

Make a plot benchmark.png showing $t_{SVD}$ and $t_{QR}$ versus $i.$

Print to standard output the time $($in seconds$)$ of inverting a $10241024$ matrix by each method. Also print to standard output a statement about which method is the fastest.

You should try to minimize the time taken by both methods. For example, Q is an orthogonal matrix; is it faster to explicitly invert it or take it's transpose? Extra credit to anyone who can find a way of SV$-$ or QR$-$inverting a random $10241024$ matrix faster than the instructor.