# On Solving Pentadiagonal Linear Systems via Transformations

Authors: S. S. Askar; A. A. Karawia
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Many authors have studied numerical algorithms for solving the linear systems of pentadiagonal type. The well-known fast pentadiagonal system solver algorithm is an example of such algorithms. The current paper describes new numerical and symbolic algorithms for solving pentadiagonal linear systems via transformations. The proposed algorithms generalize the algorithms presented in El-Mikkawy and Atlan, 2014. Our symbolic algorithms remove the cases where the numerical algorithms fail. The computational cost of our algorithms is better than those algorithms in literature. Some examples are given in order to illustrate the effectiveness of the proposed algorithms. All experiments are carried out on a computer with the aid of programs written in MATLAB.


---

## Body

## 1. Introduction

The pentadiagonal linear systems, denoted by (PLS), take the following forms:(1)PX=Y,where P is n-by-n pentadiagonal matrix given by(2)P=d1a1b10……………0c2d2a2b20…………0e3c3d3a3b30………00e4c4d4a4b40……0⋮⋱⋱⋱⋱⋱⋱⋱…⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮0………0en-2cn-2dn-2an-2bn-20…………0en-1cn-1dn-1an-10……………0encndn,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhihhhhhhhhn≥4,where X=(x1,x2,…,xn)t and Y=(y1,y2,…,yn)t are vectors of length n.This kind of linear systems is well known in the literature [1–11] and often these types of linear systems are widely used in areas of science and engineering, for example, in numerical solution of ordinary and partial differential equations (ODE and PDE), interpolation problems, boundary value problems (BVP), parallel computing, physics, and matrix algebra [4–14]. The authors in [7] have developed an efficient algorithm to find the inverse of a general pentadiagonal matrix. In [8], the author presented an efficient computational algorithm for solving periodic pentadiagonal linear systems. The algorithm depends on the LU factorization of the periodic pentadiagonal matrix. New algorithms are used for solving periodic pentadiagonal linear systems based on the use of any pentadiagonal linear solver. The author described a symbolic algorithm for solving pentadiagonal linear systems [9]. In [10], the authors discussed the general nonsymmetric problem and proposed an algorithm for solving nonsymmetric pentadiagonal Toeplitz linear systems. A fast algorithm for solving a large system with a symmetric Toeplitz pentadiagonal coefficient matrix has been presented [11]. This efficient method depends on the idea of a system perturbation followed by corrections and is competitive with standard methods. In [12], the authors described an efficient computational algorithm and symbolic algorithm for solving nearly pentadiagonal linear systems based on the LU factorization of the nearly pentadiagonal matrix.In this paper, we introduce more efficient algorithms based on transformations which can be described as a natural generalization of the efficient algorithms in [15].The current paper is organized as follows. In Section2, new numerical algorithms for solving a pentadiagonal linear system are presented. New symbolic algorithms for solving a pentadiagonal linear system are constructed in Section 3. In Section 4, three illustrative examples are presented. Conclusions of the work are given in Section 5.


## 2. Numerical Algorithms for Solving PLS

In this section, we will focus on the construction of new numerical algorithms for computing the solution of pentadiagonal linear system. For this purpose it is convenient to give five vectorsα=(α1,α2,…,αn-1), β=(β1,β2,…,βn-2), Z=(z1,z2,…,zn), γ=(γ2,γ3,…,γn), and μ=(μ1,μ2,…,μn), where(3)αi=a1μ1,i=1,ai-βi-1γiμi,i=2,3,…,n-1,(4)βi=biμi,i=2,3,…,n-1,(5)zi=y1μ1,i=1,y2-z1γ2μ2,i=2,yi-zi-2ei-zi-1γiμi,i=3,4,…,n,(6)γi=c2,i=2,ci-αi-2ei,i=3,4,…,n,(7)μi=d1,i=1,d2-α1γ2,i=2,di-βi-2ei-αi-1γi,i=3,4,…,n.By using those vectors together with the suitable elementary row operations, one can see that system (1) may be transformed to the equivalent linear system as follows:(8)1α1β10……………001α2β20…………0001α3β30………00001α4β40……0⋮⋱⋱⋱⋱⋱⋱⋱…⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮0………0001αn-2βn-20…………0001αn-10……………0001·x1x2x3x4⋮⋮⋮xn-2xn-1xn=z1z2z3z4⋮⋮⋮zn-2zn-1zn.The transformed system (8) is easy to solve by a backward substitution. Consequently, the PLS (1) can be solved using Algorithm 1.Algorithm 1:First numerical algorithm for solving pentadiagonal linear system.
To find the solution of PLS (1) using the transformed system (8), we proceed as follows:
INPUT Order of the matrix n and the components di,ai,bi,ci,ei,fi, i=1,2,…,n, (an=bn=bn-1=c1=e1=e2=0).
OUTPUT The solution vector X=(x1,x2,…,xn)t.
Step  1. Use DETGPENTA algorithm [14] or DETGPENTA algorithm [16] to check the non-singularity of the coefficient matrix
of the system (1).
Step  2. If det⁡(P)=0, then Exit and Print Message (“No solutions”) end if.
Step  3. Set μ1=d1, α1=a1/μ1, β1=b1/μ1, and z1=y1/μ1.
Step  4. Set γ2=c2, μ2=d2-α1γ2, α2=(a2-β1γ2)/μ2, β2=b2/μ2, and z2=(y2-z1γ2)/μ2.
Step  5. For i=3,4,…,n-2 do
Compute and simplify:
γi=ci-αi-2ei,
μi=di-βi-2ei-αi-1γi,
αi=ai-βi-1γiμi,
βi=biμi,
zi=yi-zi-2ei-zi-1γiμi,
End do.
γn-1=cn-1-αn-3en-1,
μn-1=dn-1-βn-3en-1-αn-2γn-1,
αn-1=an-1-βn-2γn-1μn-1,
γn=cn-αn-2en,
μn=dn-βn-2en-αn-1γn,
zn-1=yn-1-zn-2en-1-zn-2γn-1μn-1,
zn=yn-zn-1en-zn-1γnμn,
Step  6. Compute the solution vector X=(x1,x2,…,xn)t using xn=zn, xn-1=zn-1-αn-1xn.
Fori=n-2,n-3,…,1 do
Compute and simplify:
xi=zi-αixi+1-βixi+2
End do.The numerical Algorithm1 will be referred to as PTRANS-I algorithm in the sequel. The computational cost of PTRANS-I algorithm is 19n-29 operations. The conditions μi≠0, i=1,2,…,n, are sufficient for its validity.In a similar manner, we may consider five vectorsσ=(σ2,σ3,…,σn), ϕ=(ϕ3,ϕ4,…,ϕn), W=(w1,w2,…,wn), ρ=(ρ1,ρ2,…,ρn-1), and ψ=(ψ1,ψ2,…,ψn), where(9)σi=cnψn,i=n,ci-ϕi+1ρiψi,i=n-1,n-2,…,2,(10)ϕi=eiψi,i=n,n-1,…,3,(11)wi=ynψn,i=n,yn-1-wnρn-1ψn-1,i=n-1,yi-wi+2bi-wi+1ρiψi,i=n-2,n-3,…,1,(12)ρi=an-1,i=n-1,ai-σi+2bi,i=n-2,n-3,…,1,(13)ψi=dn,i=n,dn-1-σnρn-1,i=n-1,di-ϕi+2bi-σi+1ρi,i=n-2,n-3,…,1.Now we will present another algorithm for solving PLS. As in PTRANS-I algorithm, by using the vectors σ, ϕ, W, ρ, and ψ, together with the suitable elementary row operations, we see that system (1) may be transformed to the equivalent linear system as follows:(14)1000……………0σ21000…………0ϕ3σ31000………00ϕ4σ41000……0⋮⋱⋱⋱⋱⋱⋱⋱…⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋮0………0ϕn-2σn-21000…………0ϕn-1σn-1100……………0ϕnσn1·x1x2x3x4⋮⋮⋮xn-2xn-1xn=w1w2w3w4⋮⋮⋮wn-2wn-1wn.The transformed system (14) is easy to solve by a forward substitution. Consequently, the PLS (1) can be solved using Algorithm 2.Algorithm 2:Second numerical algorithm for solving pentadiagonal linear system.
To find the solution of PLS (1) using the transformed system (14), we proceed as follows:
INPUT Order of the matrix n and the components di,ai,bi,ci,ei,fi, i=1,2,…,n, (an=bn=bn-1=c1=e1=e2=0).
OUTPUT The solution vector X=(x1,x2,…,xn)t.
Step  1. Use DETGPENTA algorithm [14] or DETGPENTA algorithm [16] to check the non-singularity of the coefficient matrix
of the system (1).
Step  2. If det⁡(P)=0, then Exit and Print Message (“No solutions”) end if.
Step  3. Set ψn=dn, σn=cn/ψn, ϕn=en/ψn, and wn=yn/ψn.
Step  4. Set ρn-1=an-1, ψn-1=dn-1-σnρn-1, σn-1=(cn-1-ϕnρn-1)/ψn-1, ϕn-1=en-1/ψn-1, and wn-1=(yn-1-wnρn-1)/ψn-1.
Step  5. For i=n-2,n-3,…,3 do
Compute and simplify:
ρi=ai-σi+2bi,
ψi=di-ϕi+2bi-σi+1ρi,
σi=ci-ϕi+1ρiψi,
ϕi=eiψi,
wi=yi-wi+2bi-wi+1ρiψi,
End do.
ρ2=a2-σ4b2,
ψ2=d2-ϕ4b2-σ3ρ2,
σ2=c2-ϕ4ρ2ψ2,
ρ1=a1-σ3b1,
ψ1=d1-ϕ3b1-σ2ρ1,
w2=y2-w4b2-w3ρ2ψ2,
w1=y1-w3b1-w2ρ1ψ1,
Step  6. Compute the solution vector X=(x1,x2,…,xn)t using x=w1,  x2=w2-σ2x1.
Fori=3,4,…,n do
Compute and simplify:
xi=wi-σixi-1-ϕixi-2
End do.The numerical Algorithm2 will be referred to as PTRANS-II algorithm in the sequel. The computational cost of PTRANS-II algorithm is 19n-29 operations. Also, the conditions ψi≠0, i=1,2,…,n, are sufficient for its validity.Ifμi=0 or ψi=0 for any i∈{1,2,…,n} then PTRANS-I and PTRANS-II algorithms fail to solve pentadiagonal linear systems, respectively. So, in the next section, we develop two symbolic algorithms in order to remove the cases where the numerical algorithms fail. The parameter “p” in the following symbolic algorithms is just a symbolic character. It is a dummy argument and its actual value is zero.


## 3. Symbolic Algorithms for Solving PLS

In this section, we will focus on the construction of new symbolic algorithms for computing the solution of pentadiagonal linear systems. Algorithm3 is a symbolic version of PTRANS-I algorithm.Algorithm 3:First symbolic algorithm for solving pentadiagonal linear system.
To find the solution of PLS (1) using the transformed system (8), we proceed as follows:
INPUT Order of the matrix n and the components di,ai,bi,ci,ei,fi, i=1,2,…,n, (an=bn=bn-1=c1=e1=e2=0).
OUTPUT The solution vector X=(x1,x2,…,xn)t.
Step  1. Use DETGPENTA algorithm [14] or DETGPENTA algorithm [16] to check the non-singularity of the coefficient matrix
of the system (1).
Step  2. If det⁡(P)=0, then Exit and Print Message (“No solutions”) end if.
Step  3. Set μ1=d1. If μ1=0 then μ1=p end if.
Step  4. Set α1=a1/μ1, β1=b1/μ1, z1=y1/μ1 and γ2=c2.
Step  5. Set μ2=d2-α1γ2. If μ2=0 then μ2=p end if.
Step  6. Set α2=(a2-β1γ2)/μ2, β2=b2/μ2, and z2=(y2-z1γ2)/μ2.
Step  7. For i=3,4,…,n-2 do
Compute and simplify:
γi=ci-αi-2ei,
μi=di-βi-2ei-αi-1γi,
Ifμi=0 then μi=p end if.
αi=ai-βi-1γiμi,
βi=biμi,
zi=yi-zi-2ei-zi-1γiμi,
End do.
γn-1=cn-1-αn-3en-1,
μn-1=dn-1-βn-3en-1-αn-2γn-1. If μn-1=0 then μn-1=p end if.
αn-1=an-1-βn-2γn-1μn-1,
γn=cn-αn-2en,
μn=dn-βn-2en-αn-1γn. If μn=0 then μn=p end if.
zn-1=yn-1-zn-2en-1-zn-2γn-1μn-1,
zn=yn-zn-1en-zn-1γnμn,
Step  8. Compute the solution vector X=(x1,x2,…,xn)t using xn=zn, xn-1=zn-1-αn-1xn.
Fori=n-2,n-3,…,1 do
Compute and simplify:
xi=zi-αixi+1-βixi+2
End do.
Step  9. Substitute p=0 in all expressions of the solution vector xi,i=1,2,…,n.The symbolic Algorithm3 will be referred to as SPTRANS-I algorithm in the sequel.Algorithm4 gives the symbolic version of PTRANS-II algorithm.Algorithm 4:Second symbolic algorithm for solving pentadiagonal linear system.
To find the solution of PLS (1) using the transformed system (14), we proceed as follows:
INPUT Order of the matrix n and the components di,ai,bi,ci,ei,fi, i=1,2,…,n, (an=bn=bn-1=c1=e1=e2=0).
OUTPUT The solution vector X=(x1,x2,…,xn)t.
Step  1. Use DETGPENTA algorithm [14] or DETGPENTA algorithm [16] to check the non-singularity of the coefficient matrix
of the system (1).
Step  2. If det⁡(P)=0, then Exit and Print Message (“No solutions”) end if.
Step  3. Set ψn=dn. If ψn=0 then ψn=p end if.
Step  4. σn=cn/ψn, ϕn=en/ψn, wn=yn/ψn and ρn-1=an-1.
Step  5. Set ψn-1=dn-1-σnρn-1. If ψn-1=0 then ψn-1=p end if.
Step  6. σn-1=(cn-1-ϕnρn-1)/ψn-1, ϕn-1=en-1/ψn-1, and wn-1=(yn-1-wnρn-1)/ψn-1.
Step  7. For i=n-2,n-3,…,3 do
Compute and simplify:
ρi=ai-σi+2bi,
ψi=di-ϕi+2bi-σi+1ρi,
Ifψi=0 then ψi=p end if.
σi=ci-ϕi+1ρiψi,
ϕi=eiψi,
wi=yi-wi+2bi-wi+1ρiψi,
End do.
ρ2=a2-σ4b2,
ψ2=d2-ϕ4b2-σ3ρ2. If ψ2=0 then ψ2=p end if.
σ2=c2-ϕ4ρ2ψ2,
ρ1=a1-σ3b1,
ψ1=d1-ϕ3b1-σ2ρ1. If ψ1=0 then ψi=p end if.
w2=y2-w4b2-w3ρ2ψ2,
w1=y1-w3b1-w2ρ1ψ1,
Step  8. Compute the solution vector X=(x1,x2,…,xn)t using x=w1,  x2=w2-σ2x1.
Fori=3,4,...,n do
Compute and simplify:
xi=wi-σixi-1-ϕixi-2
End do.
Step  9. Substitute p=0 in all expressions of the solution vector xi,i=1,2,…,n.The symbolic Algorithm4 will be referred to as SPTRANS-II algorithm in the sequel.Corollary 1 (generalization version of Corollary 2.1 in [15]).
LetP^ be the backward matrix of the pentadiagonal matrix P in (2) and be given by(15)P^=0……………0b1a1d10…………0b2a2d2c20………0b3a3d3c3e30……0b4a4d4c4e40⋮…⋰⋰⋰⋰⋰⋰⋰⋮⋮⋰⋰⋰⋰⋰⋰⋰…⋮⋮⋰⋰⋰⋰⋰⋰……⋮bn-2an-2dn-2cn-2en-20………0an-1dn-1cn-1en-10…………0dncnen0……………0,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhn≥4.Then the backward pentadiagonal linear system(16)P^V=Y,V=v1,v2,…,vnthas the solution vi=xn-i+1, i=1,2,…,n, where j is the floor function of j and X=(x1,x2,…,xn)t is the solution vector of the linear system (1).Proof.
Consider then×n permutation matrix M defined by(17)M=0⋯⋯01⋮10⋮⋰⋮01⋮10⋯⋯0.For this matrix, we have(18)M-1=M.Since(19)P^=PMthen, using (18) and (19), the result follows.Corollary 2 (generalization version of Corollary 2.2 in [15]).
The determinants of the coefficient matricesP and P^ in (2) and (15) are given, respectively, by(20)det⁡P=∏i=1n‍μi=∏i=1n‍ψi,det⁡(P^)=-1n(n-1)/2∏i=1n‍μi=(-1)nn-1/2∏i=1nψi,where μ1,μ2,…,μn and ψ1,ψ2,…,ψn satisfy (7) and (13), respectively.Proof.
Using (8), (14) and (19) complete the proof.


## 4. Illustrative Examples

In this section, we give three examples for the sake of illustration. All experiments were performed in MATLAB R2014a with an Intel Core i7-4700MQ CPU@2.40 GHz 2.40 GHz.Example 1 (Case I:μi≠0 and ψi≠0 for all i).
Find the solution of the following pentadiagonal linear system of size 10:(21)121000000032250000001231-200000031-451000000125-7500000051632000000227-1400000021-14-30000002-2150000000-148·x1x2x3x4x5x6x7x8x9x10=8338242982711757108.Solution. We have n=10, d=(1,2,3,-4,5,6,7,-1,1,8)t, a=(2,2,1,5,-7,3,-1,4,5)t, b=(1,5,-2,1,5,2,4,-3)t, c=(0,3,2,1,2,1,2,1,-2,4)t, e=(0,0,1,3,1,5,2,2,2,-1)t, and y=(8,33,8,24,29,98,99,17,57,108)t.(i)
Applying the PTRANS-I algorithm, it yields
(a)
μ
=
(
1
,
-
4,2
,
-
3
/
8, 27, 245/9, 3289/441, -335/383, -2897/484, 3439/279)t, and det⁡(P)=∏i=110‍μi=4989610795975/4701708;
(b)
PTRANS-I(n,d,a,b,c,e,y) = (1,2,3,4,5,6,7,8,9,10)t.
(ii)
Applying the PTRANS-II algorithm, it yields
(a)
ψ
=
(
-
6213
/
3613, 1603/1405, 1487/433, -5173/239, 383/156, 988/161, 69/11, -77/12, -3/2,8)t, and det⁡(P)=∏i=110ψi=557494642026514353/525327436055;
(b)
PTRANS-II(n,d,a,b,c,e,y) = (1,2,3,4,5,6,7,8,9,10)t.Example 2 (Case II:μi=0 and ψi=0 for some i).
Find the solution of the following pentadiagonal linear system of size 4:(22)3210-3-27132-150123x1x2x3x4=6396.Solution. We have n=4, d=(3,-2,-1,3)t, a=(2,7,5)t, b=(1,1)t, c=(0,-3,2,2)t,e=(0,0,3,1)t, and y=(6,3,9,6)t.The numerical algorithms PTRANS-I and PTRANS-II fail to solve the pentadiagonal linear system (22) since μ2=0.(i)
Applying the SPTRANS-I algorithm, it yields
(a)
μ=(3,p,-2,(8p-21)/p)t, det⁡(P)=(∏i=14‍μi)p=0=126;(b)
SPTRANS-I(n,d,a,b,c,e,y) = (((25p-42)/(16p-42),-21/(8p-21), 21(p-2)/2(8p-21), and (9p-21)/(8p-21))t)p=0=(1,1,1,1)t.(ii)
Applying the SPTRANS-II algorithm, it yields
(a)
ψ=(21/4,-24/13,-13/3,3)t, det⁡(P)=∏i=14‍ψi=126;(b)
SPTRANS-II(n,d,a,b,c,e,y) = (1,1,1,1)t.Example 3.
We consider the followingn×n pentadiagonal linear system in order to demonstrate the efficiency of Algorithms 3 and 4:(23)9-410⋯⋯⋯⋯⋯0-46-41001-46-410001-46-41⋱0⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱0⋮01-46-41⋮01-45-20⋯⋯⋯⋯⋯01-21·x1x2x3x4⋮⋮⋮xn-2xn-1xn=6-100⋮⋮⋮000.Analytically, one can see that the exact solution of the above system isx=(1,1,…,1)t. In Table 1, we give some comparisons between our proposed algorithm and the state-of-the-art algorithms in literature. Table 1 shows solutions obtained by our proposed algorithms and other algorithms in literature for different sizes. Our obtained results show that our algorithm PTRANS-II gives better absolute error than those algorithms used in comparisons for large values of n. Moreover the obtained results indicate that the value of the running time for Algorithm3 [9] is small in comparison with other algorithms for large sizes.Table 1
Comparisons between our proposed algorithms and state-of-the-art algorithms in literature.
n
x
-
x
-
∞ and CPU time (S)
PTRANS-I
PTRANS-II
Algorithm  3 [9]
A
∖
b (MATLAB)
SYMPENTAINV [7]
500
1.5856 × 10−7
0.0069
0
0.0086
6.8579 × 10−8
0.0048
9.98 × 10−8
0.0023
1.5881 × 10−7
0.3317
5000
8.3674 × 10−4
0.0062
0
0.0391
3.0253 × 10−4
0.0057
2.50 × 10−4
0.7548
8.3654 × 10−4
108.0919
10000
0.0058
0.0114
0
0.0511
0.0052
0.0101
0.0106
4.5464
0.0058
812.9783
50000
2.1415
0.0308
0
0.1687
7.9056
0.0119
0.0159
655.51
—
—


## 5. Conclusion

There are many numerical algorithms that have been used for solving linear systems of pentadiagonal type. All numerical algorithms including the PTRANS-I and PTRANS-II algorithms of the current paper fail to solve the pentadiagonal linear system ifμi=0 and ψi=0 for any i∈{1,2,…,n}. The symbolic algorithms SPTRANS-I and SPTRANS-II of the current paper are constructed in order to remove the cases where the numerical algorithms fail. Using numerical examples we have obtained that SPTRANS-II algorithm works as well as Algorithm3  [9] and (A∖y) MATLAB algorithms. Hence, it may become a useful tool for solving linear systems of pentadiagonal type.



---

*Source: 232456-2015-03-31.xml*