shifted linear systems.

Now we consider the computational costs of Algorithm 2.1 for a large number of complex symmetric shifted linear systems, i.e., $m\gg1$. For the case $m\gg1$ we readily see from Algorithm 2.1 that computing the recurrences for updating approximate solutions is the most time-consuming part due to a cost of $6Nm+3m$ per iteration step. Hence we will now consider a weight to reduce the computational cost for the recurrences of ${\mbox{\boldmath $x$}}_n^{(\ell)}$. To achieve this we propose the following choice: $$\begin{aligned}
  W_{n+1}=L_{n+1}^{(\ell)}\ {\textrm}{such that}\ L_{n+1}^{(\ell)}T_{n+1,n}^{(\ell)}=
\pmatrix{B_n^{(\ell)} \cr \mathbf{0}^T},   \label{bidiagonal_weight}\end{aligned}$$ where $B_n^{(\ell)}$ is an $n$-by-$n$ upper bidiagonal matrix of the form $$\begin{aligned}
B_{n}^{(\ell)}:=
\pmatrix{
t_{1,1}^{(\ell)}& t_{1,2}^{(\ell)} &        &       \cr
                & t_{2,2}^{(\ell)} & \ddots &       \cr
                &          &         \ddots &   t_{n-1,n}^{(\ell)} \cr
                &          &                &   t_{n,n}^{(\ell)}},\end{aligned}$$ and $L^{(\ell)}_{n+1}$ is lower triangular and will be specified below.

Next we derive recurrence formulas for updating the approximate solutions ${\mbox{\boldmath $x$}}_n^{(\ell)}$. From (\[WLSP\]) with the choice $W_{n+1}=L_{n+1}^{(\ell)}$ of (\[bidiagonal\_weight\]) it follows that $$\begin{aligned}
{\mbox{\boldmath $y$}}_n^{(\ell)}  &=& \arg\min_{{\mbox{\boldmath $z$}}_n^{(\ell)}\in \mathbf{C}^n}\ \Bigl\| g_1 {\mbox{\boldmath $e$}}_1- T_{n+1,n}^{(\ell)}{\mbox{\boldmath $z$}}_n^{(\ell)}\Bigr\|_{(L_{n+1}^{(\ell)})^{\textrm{\scriptsize{H}}}L_{n+1}^{(\ell)}} \label{WLSP_B}\\
                &=& \arg\min_{{\mbox{\boldmath $z$}}_n^{(\ell)}\in \mathbf{C}^n}\ \Bigl\| g_1  L_{n+1}^{(\ell)}{\mbox{\boldmath $e$}}_1-  L_{n+1}^{(\ell)}T_{n+1,n}^{(\ell)}{\mbox{\boldmath $z$}}_n^{(\ell)}\Bigr\|_{2}      \nonumber\\
                &=& \arg\min_{{\mbox{\boldmath $z$}}_n^{(\ell)}\in \mathbf{C}^n}\ \biggl\| 
\pmatrix{\widetilde{{\mbox{\boldmath $g$}}}_n^{(\ell)} \cr \widetilde{g}_{n+1}^{(\ell)}}
- \pmatrix{B_n^{(\ell)} \cr \mathbf{0}^{\textrm{\scriptsize{T}}}}
  {\mbox{\boldmath $z$}}_n^{(\ell)}\biggr\|_2, \ 