comment
Efficient solution to a structured symmetric linear system with condition number estimation
It seems OP is happy with this answer. But I'll mention a few avenues for improving things further. It may be possible to scale the original matrix to reduce the condition number before doing the LU factorization. See LAPACK's DGEEQU routine for an example. If the matrix is still close to singular, you could use a partial or full pivoting approach in the $L_{22} U_{22}$ step to help, and also reveal the rank of the matrix.
revised
Efficient solution to a structured symmetric linear system with condition number estimation
added 518 characters in body
Loading…
answered
Loading…
awarded
comment
Derivative-free ill-conditioned non-linear least squares
What is the reason for the ill-conditioning? If its related to a lack of data, it may be necessary to introduce a prior in the form of some regularization constraint.
comment
Derivative-free ill-conditioned non-linear least squares
You're asking for a derivative-free solver but then mention the Jacobian? The Jacobian by definition is the derivative of the objective function residuals. The TSVD and Tikhonov methods would require a Jacobian matrix. So do you have a Jacobian available or not?
comment
FEM and High Performance Computing
One possible reason is that these libraries require C++ which not all of us are familiar with. Is it possible to use these libraries coming from a C or Fortran background?
comment
How to debug segmentation faults in large problems?
If you're running on 4 cores,you might as well try the LAPACK routine DPOTRF. Another thing to check, is the array you pass in to the cholesky routine properly allocated? Maybe you're allocating enough space for the 50k matrix but not the 100k?
comment
Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero
When solving the triangle systems, you can certainly use the sparseness of $b$. Davis' book on sparse matrix methods is one reference.
comment
Solving a sparse linear system using transpose of lower triangular matrix without copying
Here is a C implementation for CSC format: github.com/DrTimothyAldenDavis/SuiteSparse/blob/master/CSparse/…
comment
Is LAPACK behind the cutting edge of dense linear algebra?
The cited paper says the break even point is about $n=800$
comment
Is LAPACK behind the cutting edge of dense linear algebra?
LAPACK 3.9.0 was released in November 2019, netlib.org/lapack/lapack-3.9.0.html. it is actively developed, and I doubt you will find a more state of the art dense linear algebra library available.
comment
Algorithm to factorize matrix whose many rows are already of upper triangular form?
You mentioned you are using python, which I am not too familiar with. But for step 3, it is important that you use the proper TRSM BLAS call to take advantage of the triangular structure of $U_{11}$. Hopefully python will allow you to call the appropriate low-level BLAS routines.
comment
Algorithm to factorize matrix whose many rows are already of upper triangular form?
I should have mentioned, a C implementation of recursive LU can be found here: git.savannah.gnu.org/cgit/gsl.git/tree/linalg/lu.c -- see the routine LU_decomp_L3. Of course, you don't really need a fully recursive algorithm, you are just doing the first step of the recursion, taking advantage of the special matrix structure, and then calling a conventional LU algorithm
comment
Algorithm to factorize matrix whose many rows are already of upper triangular form?
I agree with Frederico you could implement an efficient QR method for this matrix, similar to the gsl routine. However I recommend instead the LU approach in my answer below, since it is efficient and much easier to implement
Loading…
comment
Algorithm to factorize matrix whose many rows are already of upper triangular form?
@LAD, hmm ok I missed that your triangular matrix is not square. That would make it difficult to compute the $R$ factor in-place. So what you have is trapezoidal on top of rectangle. If you can do a small number of givens transformations to make a square triangle in top of rectangle, you can then do the efficient algorithm I referenced
comment
Algorithm to factorize matrix whose many rows are already of upper triangular form?
gnu.org/software/gsl/doc/html/… This algorithm uses a specialized QR method to factor this type of matrix, namely a modified Elmroth and Gustafson 2000 method
Loading…