The Parks and Rec department has an opening for a Solver of Linear Equations. Since Leslie is great at solving systems of linear equations she zealously offers to give all candidates a quick demonstration. She finds the LU factorization of a 2000 x 2000 matrix in 78125 seconds. She then takes another 25 seconds to apply both triangular substitutions (backward and forward) to solve the system of equations Mx = y for a given vector Y.
The candidates are supposed to estimate (without actually running any code) the time it takes to factorize and efficiently solve a similar system of linear equations Ax =b, where A is a square matrix with dimension 500, given 30 different right-hand side b vectors.

Question

contestada

Respuesta :

MrRoyal MrRoyal · Answer 1 · 2022-03-07T12:11:34+01:00

Matrix are used to show data in rows and columns

The estimated time to efficiently solve the square matrix A is 4907.8125 seconds

The given parameters are:

Matrix size = 2000 by 2000

Time = 78125 seconds

Substitution time = 25 seconds

The time to solve the matrix is dependent on the size of the matrix, while the substitution time is fixed

The size of the similar matrix is 500 by 500

The similar matrix is 1/16 smaller than the original matrix of 2000 by 2000.

So, the time to factorize the matrix is:

[tex]Time = \frac{1}{16} * 78125\ seconds[/tex]

[tex]Time = 4882.8125\ seconds[/tex]

The estimate of the time to solve the new matrix is the sum of the time to factorize it and the substitution time.

So, we have:

[tex]Total = 4882.8125\ seconds + 25\ seconds[/tex]

This gives

[tex]Total = 4907.8125\ seconds[/tex]

Hence, the estimated time to efficiently solve the square matrix A is 4907.8125 seconds