## 1 Introduction
The computer routine \(dg(A)\) will produce such a block diagonal matrix, _i.e._, \(D:=dg(A)\). Based on this idea we can consider several parallel variants of [PERSON]'s algorithm. The first variant is just the above mentioned algorithm, to which we added a supplementary step to successively block-diagonalize the matrix \(E\) (the Step 5, Algorithm 3 below). We consider also the following slight modification of update formula

\[\widetilde{E}^{+}:=E-\theta\frac{(E+D)s_{n}s_{n}^{T}}{\|s_{n}\|^{2}}.\]

By adding \(D\) to both sides of this formula, the algorithm becomes more homogeneous (the same matrix is used in both Steps 2 and 4, Algorithm 3 below). Moreover (and not in the least) for this variant, a simple and elegant proof can be given for the convergence of the generated sequence (Theorem 1). Therefore the first our variant, which will be considered as the basic algorithm, is (\(E_{0}\) is a block diagonal matrix):

```
0:\(x_{0},\ E_{0},\ nmax\)
0:\(x_{n}\)
1:For\(n=0,1,..\) Until\(convergence\) Or\(n>nmax\) Do
2:\(x_{n+1}:=x_{n}-(E_{n}+D)^{-1}F(x_{n})\);
3:\(s_{n}:=x_{n+1}-x_{n}\);
4:\(\widetilde{E}_{n+1}:=E_{n}-\theta\frac{(E_{n}\!+\!D)s_{n}s_{n}^{T}}{\|s_{n}\|^{ 2}}\);
5:\(E_{n+1}:=dg(\widetilde{E}_{n+1})\). 6. End
```

**Algorithm 3**

A variant of Algorithm 3 can be obtained by applying the Sherman-Morrison lemma to avoid the inversion of a matrix in Step 2. It results the following Algorithm 4 (\(B_{0}\) is a block diagonal matrix):```
0:\(x_{0},\ B_{0},\ nmax\)
0:\(x_{n}\)
1:For\(n=0,1,..\)Until\(convergence\)Or\(n>nmax\)Do
2:\(x_{n+1}:=x_{n}-B_{n}F(x_{n})\);
3:\(s_{n}:=x_{n+1}-x_{n}\);
4:\(\widetilde{B}_{n+1}:=(I+\dfrac{\theta}{1-\theta}\dfrac{s_{n}s_{n}^{T}}{\|s_{n}\| ^{2}})B_{n}\):
5:\(B_{n+1}:=dg(\widetilde{B}_{n+1})\). 6.End
```  
**Algorithm 4**. The simplest way to design a similar parallel algorithm for the nonlinear case is to replace \(D\) in the basic algorithm with the diagonal block of the Jacobian of \(F\), \(D\ =\ D(x)=\ dg(J(x))\). It results the following Algorithm 5 for the nonlinear case:  
```
0:\(x_{0},\ E_{0},\ nmax\)
0:\(x_{n}\)
1:For\(n=0,1,..\)Until\(convergence\)Or\(n>nmax\)Do
2:\(x_{n+1}:=x_{n}-(E_{n}+D(x_{n}))^{-1}F(x_{n})\);
3:\(s_{n}:=x_{n+1}-x_{n}\);
4:\(\widetilde{E}_{n+1}:=E_{n}-\theta\dfrac{(E_{n}+D(x_{n}))s_{n}s_{n}^{T}}{\|s_{n} \|^{2}}\);
5:\(E_{n+1}:=dg(\widetilde{E}_{n+1})\). 6.End
```  
**Algorithm 5**. **Remark 1**. : _The formal replacement of \(D\) with \(D(x_{n})\) is based on the mean value theorem \(F(x_{n+1})\approx F(x_{n})+J(x_{n})(x_{n+1}-x_{n})\). However, the convergence properties of Algorithm 5, including its specific conditions, rate of convergence, etc., must be further analyzed as well. The numerical experiments (Section 5) performed so far for certain nonlinear systems show a comparable behavior of the two Algorithms (3 and 5) for the linear and nonlinear case._  
The main processing of the Algorithms 3, 5, is the computation of \((E_{n}+D)^{-1}\) or the solution of a corresponding linear system. Taking into account that \(E_{n}+D\) is a block diagonal matrix, \(E_{n}+D=diag((E_{n}+D)_{1},...,(E_{n}+D)_{p})\), where \((E_{n}+D)_{i}\), \(i=1,...,p\), are matrices of dimension \(m_{i}\), we have to perform \(p\) subtasks, whose main processing is \((E_{n}+D)_{i}^{-1}\). It is obvious that these subtasks can be done in parallel. The successive updates of the matrix \(E\), Steps 4 and 5, can also be executed in parallel. The concrete parallel implementation of this algorithm is an interesting problem and is left for a future research. As usual \(\mathcal{R}^{m\times m}\) denotes the set of square \(m\times m\) real matrices. We use \(\|\cdot\|\) and \(\|\cdot\|_{F}\) to denote the spectral and Frobenius norm respectively. The properties of Algorithm 3 are based on the following two lemmas. **Lemma 1**. : _Let \(D\in\mathcal{R}^{m\times m}\) be a block diagonal matrix (conforming with \(\mathcal{P}\)).