Preconditioned progressive iterative approximation for tensor product Said-Ball patches

doi:10.3785/j.issn.1008-9497.2022.06.006

Journal of Zhejiang University (Science Edition)

2022, Vol. 49

Issue (6): 682-690 DOI: 10.3785/j.issn.1008-9497.2022.06.006

Mathematics and Computer Science

Preconditioned progressive iterative approximation for tensor product Said-Ball patches

Haorong QUAN,Chengzhi LIU(

),Juncheng LI,Lian YANG,Lijuan HU

College of Mathematics and Finance，Hunan University of Humanities，Science and Technology，Loudi 417000，Hunan Province，China

Download:

HTML( 8 )

PDF(6412KB)
Export: BibTeX | EndNote (RIS)

Abstract

In order to accelerate the convergence of progressive iterative approximation (PIA) for tensor product Said-Ball patches, the preconditioning technique for PIA for tensor product Said-Ball patches is studied. Firstly, the diagonally compensate reduction is used to construct the preconditioner, then combined with the properties of Kronecker, the preconditioned progressive iterative approximation (PPIA) for tensor product Said-Ball patches is exploited. To further reduce the amount of calculation and improve the stability of the algorithm, the generalized minimal residual method is employed to inexactly solve the preconditioned equations and yield the inexact version of PPIA. The convergence of the PPIA and its inexact version are analyzed. Finally, numerical results illustrate that the proposed preconditioner can greatly reduce the spectral radii of PPIA's iteration matrices, hence accelerating the convergence rate of PPIA and its inexact version. Besides, since the preconditioner can improve the spectral distribution of the collocation matrix, it can also be used in the preprocess of the generalized minimal residual method to improve its convergence.

Key words： Said-Ball patch preconditioning technique progressive iterative approximation (PIA) generalized minimal residual method

Received: 12 July 2021 Published: 23 November 2022

CLC:

TP 391

Corresponding Authors: Chengzhi LIU E-mail: it-rocket@163.com

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Haorong QUAN
	Chengzhi LIU
	Juncheng LI
	Lian YANG
	Lijuan HU

Cite this article:

Haorong QUAN,Chengzhi LIU,Juncheng LI,Lian YANG,Lijuan HU. Preconditioned progressive iterative approximation for tensor product Said-Ball patches. Journal of Zhejiang University (Science Edition), 2022, 49(6): 682-690.

URL:

https://www.zjujournals.com/sci/EN/Y2022/V49/I6/682

张量积型Said-Ball曲面的预处理渐近迭代逼近法

为加快张量积型 Said-Ball曲面渐近迭代逼近法的收敛速度，探讨了张量积型Said-Ball曲面渐近迭代逼近法的预处理技术。首先利用对角补偿约化技术构造了预处理子，然后结合矩阵Kronecker积性质，采取预处理渐近迭代逼近法求解张量积型Said-Ball曲面。为进一步降低计算量并提高算法的稳定性，利用广义极小残差法求解预处理方程，得到预处理渐近迭代逼近法的非精确求解方法。分析了预处理渐近迭代逼近法及非精确求解方法的收敛性。最后用数值实例说明预处理子能大大减小迭代矩阵的谱半径，令预处理技术及其非精确求解方法的计算效率明显提高。此外，由于对角补偿预处理子能改善配置矩阵的谱分布，因此也可用于对广义极小残差法的预处理，以改善其收敛性。

关键词： Said-Ball曲面, 预处理技术, 渐近迭代逼近法, 广义极小残差法

半带宽	例1	例2	例3	例4
$q 1$	2	2	7	21
$q 2$	2	3	7	27

Table 1 Half-bandwidth of preconditioners in examples 1 to 4

Fig.1 Spectral distributions of iteration matrices of PIA， WPIA and PPIA in examples 1 to 3

Table 2 Spectral radius of iteration matrices in examples 1 to 3

k	WPIA		PPIA		GMRES		P-GMRES
k	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s
0	7.18×10^-1	-	7.18×10^-1	-	3.04×10^-14	0.091 9	2.51×10^-15	0.030 7
1	1.26×10^-1	-	4.97×10^-16	0.003 3
5	3.96×10^-2	-
10	4.56×10^-3	-
101	8.88×10^-16	0.004 4

Table 3 Interpolation errors and runtime of WPIA， PPIA， GMRES and P-GMRES in example 1

k	WPIA		PPIA		GMRES		P-GMRES
k	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s
0	3.11	-	3.11	-	6.51×10^-3	0.089 2	3.55×10^-15	0.037 3
1	2.07	-	1.99×10^-15	0.003 4
5	1.08	-
10	8.00×10^-1	-
20	5.88×10^-1	-
1 365	9.34×10^-15	0.005 3

Table 4 Interpolation errors and runtime of WPIA， PPIA， GMRES and P-GMRES in example 2

k	WPIA		PPIA		GMRES		P-GMRES
k	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s
0	1.34	-	1.34	-	3.49×10^-2	0.062 1	5.72×10^-7	0.085 7
1	7.73×10^-1	-	2.16×10^-3	-
5	5.33×10^-3	-	3.34×10^-5	-
10	3.22×10^-1	-	1.21×10^-6	-
20	1.65×10^-1	-	4.48×10^-9	0.009 7
90 721	3.56×10^-2	0.003 2

Table 5 Interpolation errors and runtime of WPIA， PPIA， GMRES and P-GMRES in example 3

k	WPIA		IPPIA-GMRES		IPPIA-CG		GMRES		P-GMRES
k	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s	$ε (k)$	T/s
0	2.48×10^-1	-	2.48×10^-1	-	2.48×10^-1	-	1.22×10^-2	0.19	3.72×10^-1	0.24
1	2.59×10^-1	-	8.05×10^-3	-	1.03×10^-2	0.93
2	2.01×10^-1	-	3.53×10^-3	-
5	8.98×10^-2	-	4.46×10^-4	-
6	8.32×10^-2	-	3.67×10^-4	0.89
10	4.08×10^-2	-
470	3.62×10^-4	3.57

Table 6 Interpolation errors and runtime of IPPIA-GMRES and the other methods in Example 4

Fig.2 Said-Ball interpolation patches in example 1

Fig.3 Said-Ball interpolation patches in example 2

Fig.4 Said-Ball interpolation patches in example 3

Fig.5 Said-Ball interpolation patches in example 4


[1]	MARCO A， MARTÍNEZ J. A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems［J］. Linear Algebra and Its Applications， 2007， 422（2/3）： 616-628. DOI：10.1016/j.laa.2006. 11.020 doi: 10.1016/j.laa.2006. 11.020

[2]	MARCO A， MARTÍNEZ J. Accurate computations with totally positive Bernstein-Vandermonde matrices［J］. Electronic Journal of Linear Algebra， 2013， 26（6）： 357-380. DOI：10.13001/1081-3810.1658 doi: 10.13001/1081-3810.1658

[3]	MARCO A， MARTÍNEZ J. Accurate computations with Said-Ball-Vandermonde matrices［J］. Linear Algebra and Its Applications， 2010， 432（11）： 2894-2908. DOI：10.1016/j.laa.2009.12.034 doi: 10.1016/j.laa.2009.12.034

[4]	刘晓艳，邓重阳. 非均匀三次B样条曲线插值的Jacobi-PIA算法［J］. 计算机辅助设计与图形学学报， 2015， 27（3）： 485-491. LIU X Y， DENG C Y. Jacobi-PIA algorithm for non-uniform cubic B-spline curve interpolation［J］. Journal of Computer-Aided Design & Computer Graphics， 2015， 27（3）： 485-491.

[5]	王志好，李亚娟，邓重阳. GS-PIA算法的收敛性证明［J］. 计算机辅助设计与图形学学报， 2018， 30（11）： 2035-2041. DOI：10.3724/SP.J.1089.2018. 17099 WANG Z H， LI Y J， DENG C Y. Convergence proof of GS-PIA algorithm［J］. Journal of Computer-Aided Design & Computer Graphics， 2018， 30（11）： 2035-2041. DOI：10.3724/SP.J.1089. 2018.17099 doi: 10.3724/SP.J.1089. 2018.17099

[6]	CARNICER J M， DELGADO J， PEÑA J M. Richardson method and totally nonnegative linear systems［J］. Linear Algebra and Its Applications， 2010， 433（11/12）： 2010-2017. DOI：10.1016/j.laa.2010.07.007 doi: 10.1016/j.laa.2010.07.007

[7]	CARNICER J M， DELGADO J， PEÑA J M. On the progressive iteration approximation property and alternative iterations［J］. Computer Aided Geometric Design， 2011， 28（9）： 523-526. DOI：10.1016/j.cagd.2011.09.005 doi: 10.1016/j.cagd.2011.09.005

[8]	蔺宏伟. 几何迭代法及其应用综述［J］. 计算机辅助设计与图形学学报， 2015， 27（4）： 582-589. LIN H W. Survey on geometric iterative methods with applications［J］. Journal of Computer-Aided Design & Computer Graphics， 2015， 27（4）： 582-589.

[9]	LIN H W， MAEKAWA T， DENG C Y. Survey on geometric iterative methods and their applications［J］. Computer-Aided Design， 2018， 95： 40-51. DOI：10.1016/j.cad.2017.10.002 doi: 10.1016/j.cad.2017.10.002

[10]	齐东旭，田自贤，张玉心，等. 曲线拟合的数值磨光方法［J］. 数学学报， 1975， 18（3）： 173-184. QI D X， TIAN Z X， ZHANG Y X， et al. The method of numeric polish in curve fitting［J］. Acta Mathematica Sinica， 1975， 18（3）： 173-184.

[11]	LIN H W， BAO H J， WANG G J. Totally positive bases and progressive iteration approximation［J］. Computers & Mathematics with Applications， 2005， 50（3/4）： 575-586. DOI：10.1016/j.camwa. 2005.01.023 doi: 10.1016/j.camwa. 2005.01.023

[12]	LU L Z. Weighted progressive iteration approximation and convergence analysis［J］. Computer Aided Geometric Design， 2010， 27（2）： 129-137. DOI：10. 1016/j.cagd.2009.11.001 doi: 10. 1016/j.cagd.2009.11.001

[13]	张莉，赵林，檀结庆. 带互异权值的渐进迭代逼近算法及其应用［J］. 浙江大学学报（理学版）， 2017， 44（1）： 22-27. DOI：10.3785/j.issn.1008-9497. 2017.01.003 ZHANG L， ZHAO L， TAN J Q. Progressive iterative approximation with different weights and its application［J］. Journal of Zhejiang University（Science Edition）， 2017， 44（1）： 22-27. DOI：10. 3785/j.issn.1008-9497.2017.01.003 doi: 10. 3785/j.issn.1008-9497.2017.01.003

[14]	张莉，陆中华，赵林，等. 带多权值局部插值型的几何迭代法［J］. 计算机辅助设计与图形学学报， 2018， 30（9）： 1699-1704. DOI：10.3724/SP.J.1089.2018. 16863 ZHANG L， LU Z H， ZHAO L， et al. Local interpolation type of geometric iterative method with multiple weights［J］. Journal of Computer-Aided Design & Computer Graphics， 2018， 30（9）： 1699-1704. DOI：10.3724/SP.J.1089.2018.16863 doi: 10.3724/SP.J.1089.2018.16863

[15]	ZHANG L， TAN J Q， GE X Y， et al. Generalized B-splines' geometric iterative fitting method with mutually different weights［J］. Journal of Computational and Applied Mathematics， 2018， 329： 331-343. DOI：10.1016/j.cam.2017.05.034 doi: 10.1016/j.cam.2017.05.034

[16]	LIU C Z， HAN X L， LI J C. The Chebyshev accelerating method for progressive iterative approximation［J］. Communications in Information and Systems， 2017， 17： 25-43. DOI：10.4310/CIS.2017.V17.N1.A2 doi: 10.4310/CIS.2017.V17.N1.A2

[17]	刘成志，韩旭里，李军成. 三次均匀B样条扩展曲线的渐进迭代逼近法［J］. 计算机辅助设计与图形学学报， 2019， 31（6）： 899-910. DOI：10.3724/SP.J. 1089.2019.17399 LIU C Z， HAN X L， LI J C. Progressive-iterative approximation by extension of cubic uniform B-spline curves［J］. Journal of Computer-Aided Design & Computer Graphics， 2019， 31（6）： 899-910. DOI：10.3724/SP.J.1089.2019.17399 doi: 10.3724/SP.J.1089.2019.17399

[18]	LIU C Z， LIU Z Y. Progressive iterative approximation with preconditioners［J］. Mathematics， 2020， 8（9）： 1503. DOI：10.3390/math8091503 doi: 10.3390/math8091503

[19]	LIU C Z， LIU Z Y， HAN X L. Preconditioned progressive iterative approximation for tensor product Bézier patches［J］. Mathematics and Computers in Simulation， 2021， 185： 372-383. DOI：10.1016/j.matcom.2021.01.002 doi: 10.1016/j.matcom.2021.01.002

[20]	DELGADO J， PEÑA J M. On the generalized Ball bases［J］. Advances in Computational Mathematics， 2006， 24（1-4）： 263-280. DOI：10. 1007/s10444-004-7636-x doi: 10. 1007/s10444-004-7636-x

[21]	HORN R A， JOHNSON C R. Topics in Matrix Analysis［M］. New York： Cambridge University Press， 1991： 239-288. doi:10.1017/cbo9780511840371 doi: 10.1017/cbo9780511840371

[1]	Xiaodong TAN,Qi ZHAO,Mingzhu WEN,Xiaochao WANG. A hybrid image watermarking algorithm based on BEMD,DCT and SVD[J]. Journal of Zhejiang University (Science Edition), 2023, 50(4): 442-454.

[2]	Yuhua FANG,Feng YE. MFDC-Net: A breast cancer pathological image classification algorithm incorporating multi-scale feature fusion and attention mechanism[J]. Journal of Zhejiang University (Science Edition), 2023, 50(4): 455-464.

[3]	Xiang KONG,Jun CHEN. A class of triangular surface of the same degree with four shape parameters[J]. Journal of Zhejiang University (Science Edition), 2023, 50(2): 153-159.

[4]	Yuanpeng ZHANG,Hongtao CHEN,Weina WANG. Nonconvex nonsmooth variational model for Poisson noise removal of gray image[J]. Journal of Zhejiang University (Science Edition), 2023, 50(2): 160-166.

[5]	Juncheng LI,Chengzhi LIU,Zhijun LUO,Zhiwen LONG. Bi-objective energy minimization of spatial parametric curves and its applications[J]. Journal of Zhejiang University (Science Edition), 2023, 50(1): 63-68.

[6]	Ruiqi YU,Yuhua LIU,Xilong SHEN,Ruyu ZHAI,Xiang ZHANG,Zhiguang ZHOU. Representation learning driven multiple graph sampling[J]. Journal of Zhejiang University (Science Edition), 2022, 49(3): 271-279.

[7]	Ruimin LYU,Taojie ZHANG,Xu XI,Mengmeng WANG,Lei MENG,Kejun ZHANG. Quantify influence of brushwork and structure on the aesthetic quality of regular script Chinese characters[J]. Journal of Zhejiang University (Science Edition), 2022, 49(3): 261-270.

[8]	Jintai ZHU,Jihua YE,Feng GUO,Lu JIANG,Aiwen JIANG. FSAGN:An expression recognition method based on independent selection of video key frames[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 141-150.

[9]	Ying ZHONG,Song WANG,Hao WU,Zepeng CHENG,Xuejun LI. SEMMA-Based visual exploration of cyber security event[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 131-140.

[10]	Qiang ZHU,Chaoyi WANG,Jiqing ZHANG,Baocai YIN,Xiaopeng WEI,Xin YANG. UAV target tracking algorithm based on event camera[J]. Journal of Zhejiang University (Science Edition), 2022, 49(1): 10-18.

[11]	Meng YANG,Shu DING,Yuntao MA,Jiayi XIE,Ruifeng DUAN. Dynamic simulation method of wheat rust based on texture feature[J]. Journal of Zhejiang University (Science Edition), 2022, 49(1): 1-9.

[12]	YU Peng, LIU Lan, CAI Yun, HE Yu, ZHANG Songhai. Home fitness monitoring system based on monocular camera[J]. Journal of Zhejiang University (Science Edition), 2021, 48(5): 521-530.

[13]	FU Rujia, XIAN Chuhua, LI Guiqing, WAN Juanjie, CAO Cheng, YANG Cunyi, GAO Yuefang. Rapid 3D reconstruction of bean plant for accurate phenotype identification[J]. Journal of Zhejiang University (Science Edition), 2021, 48(5): 531-539.

[14]	XU Min, WANG Ke, DAI Haoran, LUO Xiaobo, YU Weilun, TAO Yubo, LIN Hai. Visual analysis of cohorts and treatments of breast cancer based on electronic health records[J]. Journal of Zhejiang University (Science Edition), 2021, 48(4): 391-401.

[15]	LIN Juncong, CHEN Meng, SHI Yubin, LEI Jun, GUO Shihui, GAO Xing, LIAO Minghong, JIN Xiaogang. Personalized virtual fashion show for haute couture[J]. Journal of Zhejiang University (Science Edition), 2021, 48(4): 418-426.

Viewed

Full text

Abstract

Cited

Shared

Discussed