Suggestions about the materials on Dense Linear Algebra (Day-06)

[xinyushi]

Hello Professor Nelson,

For exercise "Use the time module to perform an experiment to verify that solve_triangular takes 𝑂(𝑛2) time. Hint: take LU decompositions of random matrices to get triangular factors of different sizes."

##############################
import time 
tlist = list()
n  = np.logspace(0,np.log10(1000), num=100) 
n = np.int64(np.round(n))
for i in n:
    A = np.random.randn(i, i)
    x = np.random.rand(i)
    b = A @ x
    P, L, U = la.lu(A)
    y = L @ x

    #Time for solve_triangular
    t0Tri = time.time()
    la.solve_triangular(L, y, lower=True)
    t1Tri = time.time()
    timeTri = t1Tri-t0Tri
    timeTri
    tlist.append(timeTri)

plt.plot(log(n),tlist, label='time vs log(n)')
plt.xlabel("n (in log) ")
plt.ylabel("Time")
plt.show()

The big-O expression for the time to run my_solve on A is O(n^3) + O(n^2). LU factorization takes O(n^3) and each inverse of a triangular matrix takes O(n^2), but two triangular matrices are still O(n^2), and then we sum them up since there is an order performing the algorithm not composed.

Here are some personal thoughts about this lecture:

For the first time I saw this lecture, I feel kind of overwhelmed since I never seen this math about different factorization before. So it might be a good idea to briefly mentioned one or two sentences about what’s the most common methods applied in different subjects to build a rough idea for the beginners. I personally think office hour discussion about it was helpful to me.

In Eigenvalue Decomposition, in the sentence “ In this case, we can write A = UAU^(H)”, it maybe better to introduce what this notation H means to clarify ambiguity. I never seen this notation before.

There are some typos which might not influence’s people’s understand but it might be nice to be corrected:
“1. Linear regresssion (example of linear system)”
This should be regression

“The pollutant is completely incaccesible (e.g. far underwater)”
This should be inaccessible

“Let 𝑝 denote the strength of the pollutant as a funciton”
This should be function

“Recall from our example that we said that you shouldn’t ever invert a matrix to solve a linear system for numerical reasons.”
Maybe change the sentence as “For numerical reasons, you should never invert a matrix to solve a linear system” to clarify.