THE WEIGHTED GS-PIA ALGORITHM FOR CUBIC B-SPLINE CURVE
INTERPOLATIONS AND CONVERGENCE ANALYSIS
ZHONGYUN LIU∗, JIAN YANG∗, XIAOFEI XU∗, MENGZHU LIN∗,AND YULIN ZHANG†
Abs ac . The weigh ed Gauss-Seidel-p og essi e i e a i e app oxima ion (WGS-PIA) algo i hm o cubic B-spline cu e
in e pola ions is conside ed in his pape . The con e gence o he WGS-PIA algo i hm is analyzed, and an uppe bound which
is s ic ly smalle han one o he con ac ion ac o o his WGS-PIA algo i hm is de i ed. I is shown ha o cubic B-spline
cu e in e pola ions, he GS-PIA algo i hm con e ges as e han he Jacobi-PIA (J-PIA) algo i hm, and ha he e always
exis s a posi i e weigh ωsuch ha he WGS-PIA con e ges as e han GS-PIA. Pa icula ly, we de i e a o mula o he
e ec i e weigh ω⋆and he “ heo e ically op imal” weigh ωm, which signi ican ly imp o es he pe o mance o he WGS-PIA
algo i hm wi h minimal addi ional cos . The nume ical expe imen s a e shown ha o a gi en e mina ion ole ance, he
numbe o i e a ions and he CPU ime equi ed by he WGS-PIA algo i hm a e less han hose equi ed by he GS-PIA
algo i hm.
Key wo ds. cu e in e pola ions; WGS-PIA algo i hm; con e gence; cubic B-spline basis; op imal weigh
AMS subjec classi ica ions. 15A48, 15A51, 65D17, 65F10
1. In oduc ion. The p og essi e i e a i e app oxima ion (PIA) me hod [10] (also called he geome ic
i e a i e me hod [11]), plays an impo an ole in cu e and su ace- i ing o a gi en se o da a poin s. This
me hod is o clea geome ic meaning, s able con e gence and simple i e a i e scheme. Abo e all, he PIA
a oids sol ing a sys em o linea equa ions di ec ly, which may cause nume ical ins abili y when he numbe
o gi en da a poin s becomes la ge . Fo hose easons, he PIA me hod and i s a ian s ha e in igued
esea che s o decades. In pa icula , he PIA me hod has been widely applied in CAGD, da a i ing and
e e se enginee ing, mesh gene a ion and so on [9, 11].
Gi en an o de ed se o da a poin s {ql}n
l=0 in R2o R3, each poin qlis assigned a pa ame e alue l
o all l= 0,1,· · · , n, and hey ollow
0= 0, l=
l−1
X
i=0
∥qi+1 −qi∥2, l = 1,· · · , n.
I is clea ha 0< 1<· · · < n. We hen de ine
−3= −2= −1= 0, n= n+1 = n+2 = n+3
o ge { l}n+3
l=−3, gene a ing he cubic B-spline basis {bl( )}n
l=0 by he de Boo -Cox o mula [21]. These
unc ions a e a se o locally e ec i e piecewise polynomial unc ions, used o cons uc complex smoo h
cu es and su aces [10, 12, 14, 18].
Th oughou his pape , all PIA- ype algo i hms a e assumed o be cubic B-spline cu e in e pola ion
algo i hms i no speci ically men ioned. The classical PIA p ocess o cubic B-spline cu e in e pola ions is
as ollows.
The PIA scheme. Se ing {p(0)
l}n
l=0 ={ql}n
l=0 ( he ini ial con ol polygon) and cons uc ing c(0)( ) =
Pn
l=0 p(0)
lbl( ) ( he ini ial in e pola ing cu e), o k= 1,2,· · · ,un il {p(k)
l}n
l=0 con e ges,
∗School o Ma hema ics and S a is ics, Changsha Uni e si y o Science and Technology, Changsha 410076, P. R. China (Liu:
[email p o ec ed]; Yang: [email p o ec ed]; Xu: [email p o ec ed]; Lin: [email p o ec ed])
†Cen o de Ma em´a ica, Uni e sidade do Minho, 4710-057 B aga, Po ugal (Yulin Zhang: [email p o ec ed]).
1
2Z. Y. Liu, J. Yang, X. F. Xu, M. Z. Lin, and Y. L. Zhang
• o compu e δ(k)
l=ql−c(k−1)( l), o l= 0,1,· · · , n;
• o upda e
p(k)
l=p(k−1)
l+δ(k)
l, o l= 0,1,· · · , n; (1.1)
• o cons uc he k- h in e pola ing cu e c(k)( ) = Pn
l=0 p(k)
lbl( ).
Eq. (1.1) gene a es he k- h con ol polygon {p(k)
l}n
l=0 and sa is ies he ollowing ela ion
p(k)
l=p(k−1)
l+ql−
n
X
j=0
p(k−1)
jbj( l), o l= 0,1,· · · , n. (1.2)
Deno e P(k)= [p(k)
0,p(k)
1,· · · ,p(k)
n]T,Q= [q0,q1,· · · ,qn]T; hen, in ma ix-ma ix o m, Eq. (1.2) can
be exp essed as ollows,
P(k)=P(k−1) + (Q−BP(k−1)), o k= 1,2,· · · ,(1.3)
whe e
B=
b0( 0)b1( 0)· · · bn( 0)
b0( 1)b1( 1)· · · b0( 0)
.
.
..
.
..
.
.
b0( n)b1( n)· · · bn( n)
(1.4)
is he colloca ion ma ix esul ing om he basis unc ions {bl( )}n
l=0 a j, j = 0,1,· · · , n. Ve y clea ly, he
PIA (1.3) is a special Richa dson i e a ion o ma ix equa ion BP=Q, see, o ins ance, e e ences [3, 16].
To accele a e he con e gence a e o PIA, some a ian s o PIA we e p oposed. Those a ian s can be
w i en as he ollowing o m
P(k)=P(k−1) +M−1(Q−BP(k−1)).(1.5)
F om he iewpoin o nume ical linea algeb a, Eq. (1.5) can be iewed as a classical spli ing i e a ion o
ma ix equa ion BP=Q, wi h he spli ing de ined as B=M−N. Usually, he ma ices M,M−1Band N
a e called p econdi ioning, p econdi ioned and esidual ma ices, espec i ely, see, o example, he e e ence
[2]. So we e e o Eq. (1.5) as he p econdi ioned PIA (PPIA). Fo example, he PPIA (1.5) becomes
• he PIA, i M=I;
• he WPIA [15], i M=1
ωI;
• he J-PIA [14], i M=D;
• he GS-PIA [18], i M=D+L;
• he PIA wi h di e en weigh s (DWPIA) [20], i M=diag(ω1,· · · , ωn+1),
whe e
B=D+L+U(1.6)
wi h L,D,Udeno ing s ic ly lowe iangula pa , diagonal pa , s ic ly uppe iangula pa o he
colloca ion ma ix B(1.4), espec i ely.
In his pape , we ocus on he accele a ion o he GS-PIA algo i hm o cubic B-spline cu e in e pola ions
[18]. Mo i a ed by he wo k o he WPIA algo i hm in [15], we conside he WGS-PIA algo i hm o cubic
B-spline cu e in e pola ions. Addi ionally, we o e a mo e succinc p oo o con e gence o bo h GS-PIA
The Weigh ed GS-PIA algo i hm 3
and J-PIA compa ed o he analyses p esen ed in [14, 18]. No ably, we demons a e ha GS-PIA exhibi s
as e con e gence a es compa ed o J-PIA.
The o ganiza ion o his pape is as ollows: a e ecalling some basic de ini ions and known esul s
in nex sec ion, we in oduce he WGS-PIA algo i hm and analyze i s con e gence in Sec ion 3, a highly
e icien weigh selec ion s a egy is in oduced and some nume ical examples a e shown in Sec ion 4, and a
b ie conclusion is ollowed in las sec ion.
No a ion. The no a ions |K|,∥K∥,ρ(K) deno e he absolu e alue, he 2-no m, and he spec al
adius o any ma ix K, espec i ely. The absolu e alue |K|is de ined as he ma ix ob ained by aking he
absolu e alue o all elemen s o K. Fo any ma ices A= (aij) and B= (bij), A > B (A≥B) means ha
aij > bij (aij ≥bij) o all indices i, j.
2. P elimina ies. In his sec ion we ecall some basic de ini ions and known esul s which will be used
la e on.
De ini ion 2.1. [1, 7] Le Zn×ndeno e he se o all eal n×nma ices which ha e all non-posi i e
o -diagonal en ies. A nonsingula ma ix A∈Zn×nis called M-ma ix i Ais a nonsingula ma ix and
A−1≥0.
De ini ion 2.2. [1] Fo an n×nma ix A= (alj ), we de ine a new ma ix ⟨A⟩= (αlj ), whe e
αlj =(|alj |, j =l
−|alj|, j =l,
and we called his ma ix ⟨A⟩ he compa ison ma ix o A.
De ini ion 2.3. [1] I ⟨A⟩is an M-ma ix, hen Ais said o be an H-ma ix.
Lemma 2.4. [1] I Ais a eal n×n H-ma ix, hen |A−1| ≤ ⟨A⟩−1.
De ini ion 2.5. [5, 7, 8] Le A=M−Nbe a spli ing. Then his spli ing is called:
• egula , i M−1≥0and N≥0;
•weak egula , i M−1≥0and M−1N≥0;
•H-spli ing i ⟨M⟩−|N|is an M-ma ix;
•H-compa ible spli ing i ⟨A⟩=⟨M⟩−|N|.
Lemma 2.6. [4] Le A−1≥0and
A=M1−N1=M2−N2
be weak egula spli ings o A. In ei he o he ollowing cases
a) N1≤N2;
b) M−1
1≥M−1
2,N1≥0;
c) M−1
1≥M−1
2,N2≥0;
he inequali y
ρ(M−1
1N1)≤ρ(M−1
2N2)
holds.
Lemma 2.7. [5] Le Abe an n×n H-ma ix.
•I he spli ing A=M−Nis an H-spli ing, hen ρ(M−1N)<1.
•I he spli ing A=M−Nis an H-compa ible spli ing, hen i is an H-spli ing.
4Z. Y. Liu, J. Yang, X. F. Xu, M. Z. Lin, and Y. L. Zhang
3. The WGS-PIA algo i hm. Le B= (D+L) + Ube a spli ing de ined as in (1.6). Simila o he
WPIA algo i hm [15], by aking M=1
ω(D+L) in Eq. (1.5), we hen ge he ollowing WGS-PIA algo i hm
P(k)=P(k−1) +ω(D+L)−1(Q−BP(k−1)),(3.1)
whe e he i e a ion ma ix is Gωgs =I−ω(D+L)−1B.
Ob iously, when ω= 1, he WGS-PIA educes o he GS-PIA. The e o e, we can expec ha he
WGS-PIA has a be e con e gence beha io han he GS-PIA o some ω.
3.1. The con e gence heo ems o he J-PIA and GS-PIA. I is shown in [12, 14, 18] ha
colloca ion ma ix B esul ing om cubic B-spline basis unc ions is a o ally nonnega i e H-ma ix. Thus,
we can gi e mo e concise p oo s o Theo em 1 in [14] and Theo em 2 in [18].
Theo em 3.1. ([14, Theo em 1], [18, Theo em 2]) Le Bin (1.4) be he colloca ion ma ix esul ing
om a cubic B-spline basis and B=D+L+Ube de ined as in (1.6). Then, he i e a ion ma ix o
he J-PIA me hod [14] is GJ=−D−1(L+U)and he i e a ion ma ix o he GS-PIA me hod [18] is
GGS =−(D+L)−1U. Fu he mo e, ρ(GJ)<1and ρ(GGS )<1.
P oo . F om he hypo hesis, we ha e ha B=D+L+Uis a o ally nonnega i e H-ma ix. Then, om
De ini ion 2.5, we ha e he spli ing B=D+ (L+U) and B= (D+L) + Ua e H-compa ible spli ings,
espec i ely. Hence, by Lemma 2.7, we ob ain ρ(GJ)<1 and ρ(GGS)<1. Thus, he p oo is comple e.
In pa icula , we obse e om he nume ical es s in [18] ha o cubic B-spline cu e in e pola ions,
he GS-PIA con e ges as e han he Jacobi-PIA. Now we gi e a heo e ical p oo .
Theo em 3.2. Unde he hypo hesis o Theo em 3.1, ρ(GGS )≤ρ(GJ).
P oo . F om he hypo hesis, we ha e ha B=D+L+Uis a o ally nonnega i e H-ma ix, which
implies D≥0, L≥0, U≥0 and D+Lbeing an H-ma ix. No e ha he i e a ion ma ix o he GS-PIA
is GGS =−(D+L)−1Uand he i e a ion ma ix o he Jacobi-PIA is GJ=−D−1(L+U). Then we ha e
ρ(GGS) = ρ((D+L)−1U)
≤ρ[|(D+L)−1||U|]
≤ρ[⟨D+L⟩−1U] (by Lemma 2.4)
=ρ[(D−L)−1U].
Since D−1≥0, (D−L)−1≥0, D−1(L+U)≥0 and (D−L)−1U≥0, so he spli ings ⟨B⟩=D−(L+U)
and ⟨B⟩= (D−L)−Ua e bo h weak egula . Due o ⟨B⟩−1≥0 and U≤L+U, by Lemma 2.6, we hen
ha e
ρ((D−L)−1U)≤ρ(D−1(L+U)) = ρ(−D−1(L+U)) = ρ(GJ).
This means ρ(GGS)≤ρ(GJ). The p oo is comple e.
3.2. The con e gence heo em. Fi s ly, we e iew Theo em 3.3 ([19, Theo ems 1-2]), he con e -
gence heo em o he ex apola ion scheme o he gene al s a iona y i e a ion me hod, as ollows.
Lemma 3.3. ([19, Theo ems 1-2]) Le S={νj=γj+iηj,j= 1,· · · , n}be he se o all eigen alues o
he i e a ion ma ix Go he s a iona y i e a ion scheme
xm+1 =Gxm+c, m = 0,1,· · · .(3.2)
Le γM, γmand ηMbe he la ges and he smalles eal pa , and he la ges magni ude imagina y pa o
eigen alues o G, espec i ely, and γm≤γj≤γM<1holds. Then
The Weigh ed GS-PIA algo i hm 5
(1) The ex apola ion scheme o (3.2)
xm+1 =Gωxm+ωc, m = 0,1,· · · ,(3.3)
whe e Gω= (1 −ω)I+ωG, con e ges i and only i 0< ω < ζ wi h ζ= minj{2(1−γj)
(1−γj)2+η2
j}.
(2) Le
ωm=ω1i ϑ ≤ψ
ω∗i ϑ ≥ψ,(3.4)
whe e ω1=1−γM
(γM−1)2+γ2
j,ω∗=2
2−(γm+γM),ϑ= (1 −γM)(γM−γm)and ψ= 2η2
M, we ha e
min
ωρ(Gω)≤ρ(Gωm) =
ηM
((γm−1)2+η2
M)1/2<1, i ωm=ω1,
[(γM−γm)2+4β2
M]1/2
2−γm−γM<1, i ωm=ω∗,
(3.5)
wi h equali y holding i (1) γM+iηM∈S, when ϑ≤ψ, o (2) γm+iηM,γM+iηM∈S, when ϑ≥ψ.
Now, we can gi e he con e gence heo em o he WGS-PIA algo i hm (3.1) o cubic B-spline cu e
in e pola ions.
Theo em 3.4. Le µj=αj+iβj,j= 1,2,· · · , n, be all eigen alues o he ma ix H= (D+L)−1B.
Le αm=min
1≤j≤n{αj},αM=max
1≤j≤n{αj},βM=max
1≤j≤n|βj|,ζ=minj{2αj
α2
j+β2
j},ϑ=αm(αM−αm),ψ= 2β2
M,
ω1=αm
α2
m+α2
M,ω∗=2
αm+αM. Then, unde he hypo hesis o Theo em 3.1, we ha e
(1) when 0< ω < ζ, he WGS-PIA (3.1) con e ges.
(2) when
ωm=ω1i ϑ ≤ψ
ω∗i ϑ ≥ψ,(3.6)
an uppe bound o he spec al adius o he i e a ion ma ix Gωgs o he WGS-PIA (3.1) eaches i s minimum,
and he ollowing ela ion
min
ωρ(Gωgs)≤
βM
(α2
m+β2
M)1/2<1, i ωm=ω1,
[(αM−αm)2+4β2
M]1/2
αm+αM<1, i ωm=ω∗,
holds.
P oo . We no ice ha H= (D+L)−1B=I+ (D+L)−1U=I−GGS. Acco ding o Theo em 3.1,
we ha e ha ρ(GGS )<1, i.e., |νj|<1, which implies γm< γj< γM<1. Thus, by Lemma 3.3, we ha e
de i ed his conclusions o (1) and (2).
Theo em 3.4 shows ha he pe o mance o he WGS-PIA algo i hm is se iously dependen on he choice
o weigh s. We ema k ha he ωmin (3.6) minimizes an uppe bound o he spec al adius o he i e a ion
ma ix Gωgs o WGS-PIA, and his ωmdoes no minimize ρ(Gωgs) i sel . Thus, i is a c ucial and challenging
ask o ind an app oxima ion ω⋆o he op imal weigh ωop ha minimizes ρ(Gωgs).
4. Nume ical expe imen s. In his sec ion, we i s p esen an inexpensi e app oach o ob ain ω⋆,
which is a nume ical app oxima ion o ωop . This app oach needs o compu e he maximum and minimum
eigen alues o Hin Theo em 3.4, which can be compu ed using he powe and in e se i e a ion me hods
[17]. Howe e , he compu a ional complexi y o hese algo i hms a e a he la ge. The e o e, exploi ing he
6Z. Y. Liu, J. Yang, X. F. Xu, M. Z. Lin, and Y. L. Zhang
s uc u e o colloca ion ma ix, we i s gi e a s a egy o ob ain he app oxima ion o hose eigen alues in
Sec ion 4.1. Nex , we es ablish he ela ionship be ween ω⋆and hose eigen alues h ough a la ge numbe
o nume ical examples in Sec ion 4.2. Finally, we gi e some nume ical examples o show he e ec i eness o
WGS-PIA in Sec ion 4.3.
4.1. App oxima ion o he eigen alues o p econdi ioned ma ix. By Theo em 3.4, we guess
ha he e is a co ela ion be ween ω⋆and ωmin (3.6). The la e equi es he p e-compu a ion o he
maximum and minimum eigen alues o he p econdi ioned ma ix H.
Fo una ely, based on he expe imen al da a so a , ω⋆changes only sligh ly when he eigen alues o H
a e sligh ly pe u bed. This enables us o app oxima ely compu e he maximum and minimum eigen alues
o H.
Since D+Lis an H-ma ix and ⟨D+L⟩=⟨D⟩−|L|, acco ding o Lemma 2.7, we can de i e ha
ρ(D−1L) = ρ(˜
L)<1. [16, Theo em 1.11] ensu es ha
(I+˜
L)−1=
∞
X
n=0
(−˜
L)n,(4.1)
Thus, he ollowing is an app oxima e o m o H:
H=(D+L)−1B
=I+ (D+L)−1U
=I+ (I+˜
L)−1˜
U
≈I+˜
U−˜
L˜
U(4.2)
wi h ˜
U=D−1Uand i s wo i ems o (4.1) a e e ained o yield (4.2).
I is clea ha only O(n) lops a e needed o compu e (4.2), which is much less han he O(n2) lops
needed o compu e H. Mo eo e , (4.2) is an uppe bidiagonal ma ix, so i s eigen alues lie on he diagonal.
Thus, i is s aigh o wa d o ob ain app oxima e maximal and minimal eigen alues o H. In con as , i
is ex emely expensi e o compu e he eigen alues o lowe Hessenbe g ma ix Hdi ec ly. To sum up, he
abo e me hod can app oxima ely de i e eigen alues o H, which consumes much less CPU ime han he
o iginal ma ix.
4.2. Compu a ion o ω⋆.Usually, ω⋆should be in he in e al ωm+1
2, ωm. Th ough nume ous
nume ical expe imen s, we obse e ha ω⋆is linea ly ela ed o ωm. Fu he mo e, by linea eg ession, we
es ablish he ollowing ma hma ical model
ω⋆=2ωm+ 1
3.(4.3)
The ollowing will show he ela ionship be ween he linea eg ession model and he sample se s. On
he A chimedes spi al o Example 4.4, we selec in e pola ion poin s o di e en sizes and pseudo- andom
en i onmen s as sample se s. Conc e ely, we use he MATLAB unc ion ng o ini ialize he Me senne
Twis e gene a o , selec ing andom numbe seeds om 1 o 5. We ob ain a o al o 100 expe imen al
sample se s {(ω(i)
m, ω(i))}i=1,··· ,100 om 20 g oups o da a poin s (n= 10,20,...,200), each con o ming o
a uni o m dis ibu ion o e [0,1]. Each ω(i)
mis compu ed by combining (4.2) and (3.6), and he ω(i) o each
sample se a e de e mined by a e sing ω(i)= 0.1:0.01 : 2, whe e a MATLAB colon is used o deno e ha
ωa e aken e e y 0.01 be ween he in e al [0.1,2]. In Fig. 4.1, Sample poin s and P edic ion cu e deno e
all 100 expe imen al sample se s {(ω(i)
m, ω(i))}i=1,··· ,100 and model cu e (4.3), espec i ely. No ice ha all
o hese sample poin s a e dis ibu ed a ound he cu e.
The Weigh ed GS-PIA algo i hm 7
1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Sample poin s
P edic ion cu e
Fig. 4.1
Compa ison o sample se s {(ω(i)
m, ω(i))}i=1,··· ,100 on he A chimedes spi al o Example 4.4
To demons a e he e ec i eness o he ω⋆in (4.3), we es ω= 0.1 : 0.01 : 2 and ω=ω⋆in
Examples 4.2 and 4.5 which a e gi en in nex subsec ion. The esul s a e displayed in Fig.4.2, whe e
ϵ(k)= max
0≤l≤n∥ck( l)−ql∥deno es he in e pola ion e o s a he k- h s ep o WGS-PIA Algo i hm (3.1),
and IT deno es he co esponding numbe o i e a ions. We obse e ha all g ay lines a e clus e ed o he
igh o he ed line, which implys ha ω⋆is a good weigh o he WGS-PIA algo i hm.
0 200 400 600 800 1000 1200
IT
10-10
10-8
10-6
10-4
10-2
100
(k)
Fig. 4.2
ϵ(k) o WGSPIA wi h di e en weigh s in Example 4.2 and 4.5
In he nex subsec ion, we use he WGS-PIA me hod wi h ω⋆in (4.3) o compu ing Examples 4.1-4.5.
All nume ical expe imen s show ha ou app oach is e ec i e. Fo mo e de ails, see subsec ion 4.3.
4.3. Nume ical examples. We use he non-uni o m cubic B-spine basis o e i y he e ec i eness
o he WGS-PIA algo i hm. Fo compa ison, we also es he GS-PIA algo i hm. The pe o mance o he
algo i hms is e alua ed by he numbe o i e a ions (IT) and he elapsed CPU ime/s (CPU/s), and CPU ime
is calcula ed by a e aging 100 epea ed expe imen s. All nume ical expe imen s we e pe o med on compu e
DESKTOP-9TC1VPG wi h 11 h Gen In el(R) Co e(TM) i5-1135G7 @ 2.40GHz by MATLAB(R2022a).
We gi e i e nume ical examples as ollows. These nume ical examples a e aken om [18] and
8Z. Y. Liu, J. Yang, X. F. Xu, M. Z. Lin, and Y. L. Zhang
h p://paulbou ke.ne /geome y/.
Example 4.1. Conside a pa ame ic unc ion gi en by
x= cos u2−cos 2u
2k+1
y= sin u2−cos 2u
2k+1
z=−sin 2u
2k+1
whe e 0 ≤u≤(4k+ 2)π. I is called Cinque oil Kno i k = 2. The 500 in e pola ion poin s on i we e
selec ed non-uni o mly.
Example 4.2. Conside he helix gi en by
x= cos(τ(θ2−θ1) + θ1)
y= sin(τ(θ2−θ1) + θ1)
z=hτ
whe e = 30, h = 50, θ1=π
6, θ2= 40π. The alue o τa 2000 in [0, 1] is uni o mly selec ed o ob ain he
in e pola ion poin s.
Example 4.3. Conside 400 in e pola ion poin s on he F ee hs Neph oid ρ= 1 + 2sin(θ/2)(0 ≤θ≤
6π).
Example 4.4. Conside he da a in e pola ion o 3000 poin s sampled om A chimedes spi al ρ=θ(0 ≤
θ≤30π).
Example 4.5. Gi en 987 sca e ed in e pola ion poin s.
We selec Examples 4.1-4.2 o he 3D cu e i s, Examples 4.3-4.5 o he 2D cu e i s. Among hem,
in e pola ion poin s o he Examples 4.1 and 4.3 a e selec ed a a smalle scale han Example 4.2 and
Example 4.4. Example 4.5 was gi en as an example o a se o sca e poin s.
In Table 4.1-4.5, we eco d he numbe o i e a ions ( he elapsed CPU ime) equi ed by GS-PIA algo-
i hm and WGS-PIA algo i hm when ϵ(k)<10−6,10−7,· · · ,10−11. The weigh ω⋆a e compu ed ia (4.3),
and i s alues(CPU ime) a e lis ed independen ly in he second column o he ables.
Table 4.1
The numbe o i e a ion s eps (CPU ime) o some gi en ole ances in Example 4.1
Algo i hm ω⋆(CPU/s) IT(CPU/s)
ϵ(k)<10−6ϵ(k)<10−7ϵ(k)<10−8ϵ(k)<10−9ϵ(k)<10−10 ϵ(k)<10−11
GS-PIA - 322(0.0296) 432(0.0387) 542(0.0492) 652(0.0594) 762(0.0679) 872(0.0796)
WGS-PIA 1.6396(0.0015) 195(0.0212) 262(0.0293) 328(0.0340) 395(0.0400) 462(0.0476) 528(0.0541)
Table 4.2
The numbe o i e a ion s eps (CPU ime) o some gi en ole ances in Example 4.2
Algo i hm ω⋆(CPU/s) IT(CPU/s)
ϵ(k)<10−6ϵ(k)<10−7ϵ(k)<10−8ϵ(k)<10−9ϵ(k)<10−10 ϵ(k)<10−11
GS-PIA - 774(1.6800) 980(2.0701) 1186(2.7445) 1391(3.3275) 1600(3.5826) 1825(3.6609)
WGS-PIA 1.4380(0.0345) 467(1.0994) 592(1.4877) 715(1.7682) 839(1.9915) 965(2.2573) 1101(2.6753)
The Weigh ed GS-PIA algo i hm 9
Table 4.3
The numbe o i e a ion s eps (CPU ime) o some gi en ole ances in Example 4.3
Algo i hm ω⋆(CPU/s) IT(CPU/s)
ϵ(k)<10−6ϵ(k)<10−7ϵ(k)<10−8ϵ(k)<10−9ϵ(k)<10−10 ϵ(k)<10−11
GS-PIA - 1113(0.0870) 1575(0.1237) 2038(0.1621) 2500(0.2039) 2962(0.2390) 3424(0.2750)
WGS-PIA 1.6601(0.0012) 670(0.0469) 948(0.0738) 1226(0.1137) 1504(0.1353) 1782(0.1589) 2060(0.1858)
Table 4.4
The numbe o i e a ion s eps (CPU ime) o some gi en ole ances in Example 4.4
Algo i hm ω⋆(CPU/s) IT(CPU/s)
ϵ(k)<10−6ϵ(k)<10−7ϵ(k)<10−8ϵ(k)<10−9ϵ(k)<10−10 ϵ(k)<10−11
GS-PIA - 1903(5.9570) 2540(7.9414) 3176(9.8952) 3812(11.8881) 4449(13.8767) 5085(15.8941)
WGS-PIA 1.6740(0.0648) 1144(4.2880) 1527(5.7635) 1909(7.0314) 2292(7.9557) 2674(9.2660) 3056(10.5765)
Table 4.5
The numbe o i e a ion s eps (CPU ime) o some gi en ole ances in Example 4.5
Algo i hm ω⋆(CPU/s) IT(CPU/s)
ϵ(k)<10−6ϵ(k)<10−7ϵ(k)<10−8ϵ(k)<10−9ϵ(k)<10−10 ϵ(k)<10−11
GS-PIA - 50(0.0282) 65(0.0340) 80(0.0402) 96(0.0474) 111(0.0549) 126(0.0647)
WGS-PIA 1.5094(0.0076) 37(0.0208) 45(0.0269) 56(0.0275) 64(0.0354) 71(0.0389) 81(0.0443)
In Figs. 4.3-4.7, we display he ini ial con ol node and hei WGS-PIA in e pola ion igu es o he 1-s
i e aion and he 10- h i e aions, as well as he ela ion diag ams o i e a ion s eps and in e pola ion e o s
o he GS-PIA and WGS-PIA.
I can be seen wi h Tables 4.1-4.5 ha , a leas om he in e pola ion e o less han 10−6, he numbe
o i e a ions o WGS-PIA is only abou 60% o ha o GS-PIA. This conclusion can be in ui i ely pe cei ed
by he g aphs in he lowe igh co ne o Figs. 4.3-4.7. Ini ially, he in e pola ion e o s o WGS-PIA a e
educed mo e slowly compa ed o GS-PIA. When ϵis oughly less han 10−4, he e o s o WGS-PIA decay
as e han ha o GS-PIA.
On he o he hand, WGS-PIA akes less CPU ime compa ed o GS-PIA wi h he same in e pola ion
e o . And in he WGS-PIA algo i hm, he compu a ion ime o ω⋆is almos negligible compa ed o he i e -
a ion ime. Since he weigh ω⋆only needs o be sol ed once in each expe imen , as he equi ed con e gence
accu acy inc eases, he pe cen age o compu a ion ime o his pa becomes inc easingly smalle .
5. Conclusions. In his pape , we ha e de eloped he WGS-PIA algo i hm by combining he GS-PIA
[18] wi h he WPIA [15]. In Theo em 3.4, we ha e shown ha he e always exis s a posi i e weigh ωsuch
ha WGS-PIA algo i hm con e ges o cubic B-spline cu e in e pola ions. Mo eo e , we ha e gi en an ωm
ha minimizes an uppe bound o he spec al adius o he i e a ion ma ix Gωgs o he WGS-PIA (3.1).
Meanwhile, we ha e gi en a mo e concisely p oo in Theo em 3.1, which shows he con e gence o he
GS-PIA [18] and he J-PIA [14] by spli ing heo ies [5]. In he nume ical expe imen s o [18], we obse ed
GS-PIA has a be e pe o mance han J-PIA o cubic B-spline cu e in e pola ions. We hen p o ed i
heo e ically, and his conclusion has been shown in Theo em 3.2.
Theo e ically, we can chose ω o be any cons an in he in e al (0, ζ) wi h ζde ined in Theo em 3.4.
