# Algorithm¶

This library provides the four kinds of numerical solvers. The kind of solvers is selected under the condition whether the Hamiltonian $${\hat H}$$ and/or the frequency $$z$$ are complex or real number. It is noted that $${\hat H}$$ must be Hermitian (symmetric) for complex (real) number.

• ($${\hat H}$$, $$z$$ ) = (complex, complex): Shifted Bi-Conjugate Gradient(BiCG) method [1]
• ($${\hat H}$$, $$z$$ ) = (real, complex): Shifted Conjugate Orthogonal Conjugate Gradient(COCG) method [2]
• ($${\hat H}$$, $$z$$ ) = (complex, real): Shifted Conjugate Gradient(CG) method (using complex vector)
• ($${\hat H}$$, $$z$$ ) = (real, real): Shifted Conjugate Gradient(CG) method (using real vector)

For above methods, seed switching [2] is adopted. Hereafter, the number of the left (right) side vector is written as $$N_L$$ ($$N_R$$). The details of each algorithm are written as follows.

## Shifted BiCG method with seed switching technique¶

$$G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)$$

do $$j = 1 \cdots N_R$$

$${\boldsymbol r} = {\boldsymbol \varphi_j}$$,

$${\tilde {\boldsymbol r}} =$$ an arbitrary vector, $${\boldsymbol r}^{\rm old} = {\tilde {\boldsymbol r}}^{\rm old} = {\bf 0}$$

$$p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)$$

$$\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0$$

do iteration

$$\circ$$ Seed equation

$$\rho^{\rm old} = \rho,\; \rho = {\tilde {\boldsymbol r}}^* \cdot {\boldsymbol r}$$

$$\beta = \rho / \rho^{\rm old}$$

$${\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}$$

$$\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\tilde {\boldsymbol r}}^*\cdot{\boldsymbol q} - \beta \rho / \alpha }$$

$$\circ$$ Shifted equation

do $$k = 1 \cdots N_z$$

$$\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)$$

do $$i = 1 \cdots N_L$$

$$p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \frac{\pi^{\rm old}_k \pi^{\rm old}_k}{\pi_k \pi_k} \beta p_{i k}$$

$$G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}$$

$$\pi_k^{\rm old} = \pi_k$$, $$\pi_k = \pi_k^{\rm new}$$

end do $$i$$

end do $$k$$

$${\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}$$

$${\boldsymbol q} = (z_{\rm seed}^* {\hat I} - {\hat H}) {\tilde {\boldsymbol r}},\; {\boldsymbol q} = \left( 1 + \frac{\alpha^* \beta^*}{\alpha^{{\rm old}*}} \right) {\tilde {\boldsymbol r}} - \alpha^* {\boldsymbol q} - \frac{\alpha^* \beta^*}{\alpha^{{\rm old} *}} {\tilde {\boldsymbol r}}^{\rm old},\; {\tilde {\boldsymbol r}}^{\rm old} = {\tilde {\boldsymbol r}},\; {\tilde {\boldsymbol r}} = {\boldsymbol q}$$

$$\circ$$ Seed switch

Search $$k$$ which gives the smallest $$|\pi_k|$$ . $$\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}$$

$${\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old},\; {\tilde {\boldsymbol r}} = {\tilde {\boldsymbol r}} / \pi_{\rm seed}^*,\; {\tilde {\boldsymbol r}}^{\rm old} = {\tilde {\boldsymbol r}}^{\rm old} / \pi_{\rm seed}^{{\rm old}*}$$

$$\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha$$, $$\rho = \rho / (\pi_{\rm seed}^{\rm old} \pi_{\rm seed}^{\rm old})$$

$$\{\pi_k = \pi_k / \pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old} / \pi_{\rm seed}^{\rm old}\}$$

if( $$|{\boldsymbol r}| <$$ Threshold) exit

end do iteration

end do $$j$$

## Shifted COCG method with seed switching technique¶

This method is obtained by $${\tilde {\boldsymbol r}} = {\boldsymbol r}^*,\; {\tilde {\boldsymbol r}}^{\rm old} = {\boldsymbol r}^{{\rm old}*}$$ in the BiCG method.

$$G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)$$

do $$j = 1 \cdots N_R$$

$${\boldsymbol r} = {\boldsymbol \varphi_j}$$, $${\boldsymbol r}^{\rm old} = {\bf 0}$$

$$p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)$$

$$\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0$$

do iteration

$$\circ$$ Seed equation

$$\rho^{\rm old} = \rho,\; \rho = {\boldsymbol r} \cdot {\boldsymbol r}$$

$$\beta = \rho / \rho^{\rm old}$$

$${\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}$$

$$\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\boldsymbol r}\cdot{\boldsymbol q} - \beta \rho / \alpha }$$

$$\circ$$ Shifted equation

do $$k = 1 \cdots N_z$$

$$\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)$$

do $$i = 1 \cdots N_L$$

$$p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \frac{\pi^{\rm old}_k \pi^{\rm old}_k}{\pi_k \pi_k} \beta p_{i k}$$

$$G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}$$

$$\pi_k^{\rm old} = \pi_k$$, $$\pi_k = \pi_k^{\rm new}$$

end do $$i$$

end do $$k$$

$${\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}$$

$$\circ$$ Seed switch

Search $$k$$ which gives the smallest $$|\pi_k|$$ . $$\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}$$

$${\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old}$$

$$\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha$$, $$\rho = \rho / (\pi_{\rm seed}^{\rm old} \pi_{\rm seed}^{\rm old})$$

$$\{\pi_k = \pi_k/\pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old} / \pi_{\rm seed}^{\rm old}\}$$

if( $$|{\boldsymbol r}| <$$ Threshold) exit

end do iteration

end do $$j$$

## Shifted CG method with seed switching technique¶

This method is obtained by $${\tilde {\boldsymbol r}} = {\boldsymbol r},\; {\tilde {\boldsymbol r}}^{\rm old} = {\boldsymbol r}^{\rm old}$$ in the BiCG method.

$$G_{i j}(z_k) = 0 (i=1 \cdots N_L,\; j = 1 \cdots N_R,\; k=1 \cdots N_z)$$

do $$j = 1 \cdots N_R$$

$${\boldsymbol r} = {\boldsymbol \varphi_j}$$, $${\boldsymbol r}^{\rm old} = {\bf 0}$$

$$p_{i k} = 0(i=1 \cdots N_L,\; k=1 \cdots N_z),\; \pi_k=\pi_k^{\rm old} = 1(k=1 \cdots N_z)$$

$$\rho = \infty,\; \alpha = 1,\; z_{\rm seed}=0$$

do iteration

$$\circ$$ Seed equation

$$\rho^{\rm old} = \rho,\; \rho = {\boldsymbol r}^* \cdot {\boldsymbol r}$$

$$\beta = \rho / \rho^{\rm old}$$

$${\boldsymbol q} = (z_{\rm seed} {\hat I} - {\hat H}){\boldsymbol r}$$

$$\alpha^{\rm old} = \alpha,\; \alpha = \frac{\rho}{{\boldsymbol r}^* \cdot {\boldsymbol q} - \beta \rho / \alpha }$$

$$\circ$$ Shifted equation

do $$k = 1 \cdots N_z$$

$$\pi_k^{\rm new} = [1+\alpha(z_k-z_{\rm seed})]\pi_k - \frac{\alpha \beta}{\alpha^{\rm old}}(\pi_k^{\rm old} - \pi_k)$$

do $$i = 1 \cdots N_L$$

$$p_{i k} = \frac{1}{\pi_k} {\boldsymbol \varphi}_i^* \cdot {\boldsymbol r} + \left(\frac{\pi^{\rm old}_k}{\pi_k } \right)^2 \beta p_{i k}$$

$$G_{i j}(z_k) = G_{i j}(z_k) + \frac{\pi_k}{\pi_k^{\rm new}} \alpha p_{i k}$$

$$\pi_k^{\rm old} = \pi_k$$, $$\pi_k = \pi_k^{\rm new}$$

end do $$i$$

end do $$k$$

$${\boldsymbol q} = \left( 1 + \frac{\alpha \beta}{\alpha^{\rm old}} \right) {\boldsymbol r} - \alpha {\boldsymbol q} - \frac{\alpha \beta}{\alpha^{\rm old}} {\boldsymbol r}^{\rm old},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r},\; {\boldsymbol r} = {\boldsymbol q}$$

$$\circ$$ Seed switch

Search $$k$$ which gives the minimum value of $$|\pi_k|$$ . $$\rightarrow z_{\rm seed},\; \pi_{\rm seed},\; \pi_{\rm seed}^{\rm old}$$

$${\boldsymbol r} = {\boldsymbol r} / \pi_{\rm seed},\; {\boldsymbol r}^{\rm old} = {\boldsymbol r}^{\rm old} / \pi_{\rm seed}^{\rm old}$$

$$\alpha = (\pi_{\rm seed}^{\rm old} / \pi_{\rm seed}) \alpha$$, $$\rho = \rho / {\pi_{\rm seed}^{\rm old}}^2$$

$$\{\pi_k = \pi_k/\pi_{\rm seed},\; \pi_k^{\rm old} = \pi_k^{\rm old}/\pi_{\rm seed}^{\rm old}\}$$

if( $$|{\boldsymbol r}| <$$ Threshold) exit

end do iteration

end do $$j$$