I have a matrix whose many rows are already in the upper triangular form.
$$\begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{5} \\ 0 & x_{22} & x_{23} & x_{24} & x_{25} \\ 0 & 0 & x_{23} & x_{34} & x_{35} \\ 0 & 0 & 0 & 0 & x_{45} \\ x_{51} & x_{52} & x_{53} & x_{54} & x_{55} \\ x_{61} & x_{62} & x_{63} & x_{64} & x_{65} \end{bmatrix}$$
Let me take an example to show that the function scipy.linalg.lu
from package Scipy
does not take advantage of this special structure. Here B
is a copy of A
with the elements below the main diagonal zeroed.
import numpy as np
import scipy.linalg as la
import time
A = np.random.randint(100, size=(10000, 10000))
B = np.triu(A, 0)
start = time.time()
(P, L, U) = la.lu(A)
end = time.time()
print('Time to decompose A =', end - start)
start = time.time()
(P1, L1, U1) = la.lu(B)
end = time.time()
print('Time to decompose B =', end - start)
The result is
Time to decompose A = 5.622066497802734
Time to decompose B = 5.322663068771362
Because my square matrix is of very large dimension and this procedure is repeated thousands of times. I would like to ask for a method (or references) to make use of this special structure to reduce the computational complexity.
Thank you so much for your help!
scipy.linalg.lu
does not make use of this special structure. In my problem, the matrix is not of upper triangular form, but it contains some rows of this form. I mean how to make use of the special structure of these rows. $\endgroup$