2
$\begingroup$

I have a linear system of complex numbers. I am using LAPACK' zgesv (actually I am using intel MKL LAPACKE, but I am assuming the algorithm is the same). No assumption can be made about the system.

I tried to follow its subroutine calls, but I got lost. What algorithm does it use, how many operations will be needed according to the size $n$ of the system?

A quick check on Wikipedia says

The cost of solving a system of linear equations is approximately $2n^3/3$

Would that be the answer? I am interested in the performance of both large and small $n$.

$\endgroup$
5
$\begingroup$

The LAPACK routine zgesv first computes the LU factorization, and then solves the system making use of the factorization. It is a simple driver for calling the two routines zgetrf (compute the LU factorization) and zgetrs (solve the system).

The LU factorization is computed using partial pivoting and row interchanges. Then, the system is solved using simple backwards and forwards substitution.

So, the number of operations needed for zgesv will be the sum of the operations for the two sub-calls. Appendix C of the installation guide for LAPACK by Blackford and Dongarra lists the operation counts needed for certain LAPACK routines. The operation counts are given for the real-valued, single precision versions. To obtain the operation counts for complex-valued versions, we notice that each complex addition is computed with two real additions, and each complex multiplication is computed with four real multiplications and two real additions.

From the installation guide: \begin{align*} \texttt{SGETRF} \qquad & \text{multiplications:}&& 1/2mn^2 - 1/6n^3+1/2mn - 1/2n^2 +2/3n \\ & \text{additions:} && 1/2mn^2 - 1/6n^3 - 1/2mn + 1/6n \\[20pt] \texttt{SGETRS} \qquad & \text{multiplications:}&& \texttt{NRHS} [n^2] \\ & \text{additions:} && \texttt{NRHS}[n^2 - n] \end{align*}

Converting to complex-valued operations, we obtain \begin{align*} \texttt{ZGETRF} \qquad & \text{multiplications:}&& 2mn^2 - 2/3n^3 + 2mn - 2n^2 + 8/3n \\ & \text{additions:} && 2mn^2 - 2/3n^3 - n^2 + 5/3n \\[20pt] \texttt{ZGETRS} \qquad & \text{multiplications:}&&\texttt{NRHS} [4n^2] \\ & \text{additions:} && \texttt{NRHS}[4n^2 - 2n] \end{align*}

Adding up: \begin{align*} \texttt{ZGESV} \qquad & \text{total:}&& 4mn^2 - 4/3n^3 + 2mn -3n^2 +13/3n + \texttt{NRHS}[8n^2 - 2n] \end{align*}

When the system is square ($m=n$) and there is only one right-hand side ($\texttt{NRHS}=1$), this reduces to $$ 8/3n^3 + 7n^2 + 7/3n. $$

$\endgroup$
  • $\begingroup$ It might be something obvious I'm missing, but why do complex numbers increase the number of multiplications by 6 times? Naively, I would think 4 times more, and I've seen ways of doing complex multiplication where it takes only 3 times more multiplications. $\endgroup$ – Tyberius Sep 4 '18 at 4:05
  • $\begingroup$ Each complex multiplication corresponds to four real multiplications and two real additions, for six total operations. You can also do it with three real multiplications and five real additions. Assuming we're doing the former, I have adjusted the answer to be more accurate in this regard. $\endgroup$ – Will P. Sep 4 '18 at 4:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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