2
$\begingroup$

My goal is to transform a matrix into upper triangular form in Python. I know the function scipy.linalg.lu will do LU decomposition and get both upper and lower triangular ones. I need to repeat this procedure several times. If there is functions from Scipy, blas, or lapack that compute only upper triangular matrix, the performance of my algorithm will be improved significantly.

Could you please suggest such functions? Thank you so much!

$\endgroup$
  • 2
    $\begingroup$ Do I understand you correctly: you want to get only $U$ from $A=LU$ factorization, while $L$ is discarded? $\endgroup$ – Anton Menshov Jun 7 at 1:09
  • $\begingroup$ Hi @AntonMenshov, for a matrix A, I can get both U, L by U, L = scipy.linalg.lu(A)[1: 3]. I can get U by U = scipy.linalg.lu(A)[2]. Even I use the latter, i.e. U = scipy.linalg.lu(A)[2], the function scipy.linalg.lu still computes L, which is unnecessary for me and takes more time. I meant to looking for a function that only computes U. $\endgroup$ – LAD Jun 7 at 6:55
7
$\begingroup$

I think you are overestimating the overhead of computing L. There are zero extra operations needed; the only additional cost is writing to RAM some numbers that you have already computed anyway. The algorithms commonly used (in Lapack, for instance) to compute U also compute L along the way, and you'd save 0 flops by omitting it.

For instance, if you think about textbook Gaussian elimination, the entry $L_{ij}$ is the multiplier $L_{ij} = A_{ij}/A_{jj}$ that you use to eliminate the zero entry in position $i,j$ at step $j$.

If you are at the point where that memory write cost matters to you, you should probably have ditched Python long ago since it is a much higher performance hit just by itself; for instance Scipy uses various un-compressed formats and does un-necessary copies of various things with respect to Lapack.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.