1
$\begingroup$

I am looking at the LAPACK DPOSV routine that computes the solution to the real system of linear equations A * X = B. The routine description can be found here:

http://www.math.utah.edu/software/lapack/lapack-d/dposv.html

How many floating point operations (flops) would a call to this routine take? What is the algorithmic complexity of this subroutine call?

$\endgroup$
  • 1
    $\begingroup$ For general matrices (i.e., no special structure), if $A$ is $n \times n$ and $B$ is $n \times m$, then you're looking at ${\cal O}(n^3) + {\cal O}(n^2 \times m)$. If you want more accurate flop counts, sum up the cost of the individual steps of the algorithms (factorization of $A$ + triangular solves). $\endgroup$ – GoHokies Nov 24 '15 at 8:37
1
$\begingroup$

There is source code of this function available here: http://www.netlib.org/lapack/explore-html/dc/de9/group__double_p_osolve.html

As you can see by following the function calls in the code, it computes the Cholesky factorization of $A$ with dpotrf, followed by dpotrs, which solves $AX=B$ by solving two triangular systems (dtrsm).

The implementations of those functions are pretty standard and should have the usual algorithmic complexities.

$\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.