Two Iterative algorithms for the matrix sign function based on the adaptive filtering technology Feng Wu1 Keqi Ye 2 Li Zhu 2 Yueling Zhao 3 Jiqiang Hu 3 and Wanxie Zhong 3

2025-05-06 0 0 526.37KB 18 页 10玖币

侵权投诉

Two Iterative algorithms for the matrix sign

function based on the adaptive filtering technology

Feng Wu*[1], Keqi Ye [2], Li Zhu [2], Yueling Zhao [3], Jiqiang Hu [3] and Wanxie Zhong [3]

[1] School of Mathematical Sciences, State Key Laboratory of Structural Analysis

of Industrial Equipment, Faculty of Vehicle Engineering and Mechanics, Dalian

University of Technology, Dalian, 116023, People's Republic of China.

[2] Department of Mechanics, Dalian University of Technology, Dalian 116023,

People's Republic of China.

[3] Faculty of Vehicle Engineering and Mechanics, State Key Laboratory of

Structural Analysis of Industrial Equipment, Dalian University of Technology, Dalian

116023, People's Republic of China

*Corresponding author:

Tel: 8613940846142; E -mail address: wufeng_chn@163.com

Abstract

In this paper, two new efficient algorithms for calculating the sign function of the

large-scale sparse matrix are proposed by combining filtering algorithm with Newton

method and Newton Schultz method respectively. Through the theoretical analysis of

the error diffusion in the iterative process, we designed an adaptive filtering threshold,

which can ensure that the filtering has little impact on the iterative process and the

calculation result. Numerical experiments are consistent with our theoretical analysis,

which shows that the computational efficiency of our method is much better than that

of Newton method and Newton Schultz method, and the computational error is of the

same order of magnitude as that of the two methods.

Key words: matrix sign function; filtering algorithm; iterative method; large-scale

sparse matrix

2010 mathematics subject classification: 65F30, 15A15

1 Introduction

In the scalar domain, the well-known sign function can be defined as

( ) ( )

( )

1, Re 0

sign 1, Re 0





=−<





Roberts extended the sign function from the scalar variable to the matrix variable

named as matrix sign function [1], which is an important matrix function with various

applications, such as Matrix Lyapunov Equations [2], Algebraic Riccati Equation (ARE)

[3-7], Stochastic Differential Equations (SDEs) [4], Yang-Baxter-like equation [8] and

so on [9-12].

For the calculation of the matrix sign function, many scholars have carried out

related research. The calculation methods for the matrix sign function include direct

methods and iterative methods. One representative method of the direct method is the

Schur Method which has excellent numerical stability. Let

nn×

∈A

have the Schur

decomposition

=A QTQ

, where

is unitary and

is the upper triangular [13],

then the Schur Method uses

( ) ( )

sign sign=A Q TQ

to evaluate the sign matrix.

Direct methods usually are costly in terms of time and space. Compared with the

direct methods, iterative methods need less computing time and storage space, and

received a lot of attention. There are many iterative methods for calculating the sign

function, among which the more famous ones are Newton’s Method, Newton–Schulz

Method, Pad´e Family of Iterations, and so on.

In addition, many scholars had constructed some effective new iterative methods

recently. As shown in Ref. [14], an iterative method with fourth-order convergence was

proposed, and its performance in numerical experiments was discussed. Ref. [4]

introduced a new iteration method to calculate the sign function of the matrix, and

proved theoretically that the algorithm is stable, and has global convergence. Ref. [8]

derived a new iteration scheme for the sign function with fourth-order convergence and

introduced the application of sign function in Yang–Baxter-like equation. Ref. [15]

proposed a new scheme, which has global convergence with eighth order of

convergence. Ref. [16] proposed a dynamics-based approach to develop efficient matrix

iterations for computing the matrix sign function. Ref. [17] proposed a direct

generalized Steffensen’s method for solving the sign function. Ref. [6] present several

parallel implementations of the matrix sign function and applied them to the continuous

time algebraic Riccati equation.

It should be noted that the above algorithms are still limited to the calculation of

the matrix with low dimension at present. Few people have studied the calculation of

large-scale matrices. Large sparse matrices will become dense when performing matrix

multiplication or matrix inversion, which makes the iterative algorithm need huge

storage space and computing time. Although matrix multiplication and inversion will

make the matrix dense, there are many elements close to zero, which have little impact

on the final calculation results, but will significantly increase the calculation time and

storage space.

One way to improve the calculation efficiency is using the filtering algorithm

[18,19,21,22]. The filtering algorithm is to construct a threshold and eliminate the

elements in the matrix whose absolute value is less than the threshold. Ref. [20] first

combined the filtering algorithm with the Newton method to calculate the approximate

inverse of the matrix. The filtering algorithm is not only applied to the calculation of

matrix inverse, but also extended to the calculation of other matrix functions (such as

matrix exponential, matrix inverse and so on) [18,19,21,22].

In this paper, the filtering algorithm is applied to the Newton Method and the

Newton Schultz Method to solve the problem of huge storage and time overhead of the

large-scale sparse matrices in calculating the sign functions. And the filtering threshold

is given theoretically.

The main structure of this paper is as follows. In Section 2, Newton’s method (NM)

and Newton–Schulz Method (NS) are introduced. In Section 3, according to the error

propagation theory, the norm upper bound to the filter matrix and the filtering threshold

are given in theory. In Section 4, numerical experiments are carried out on NMF and

NSF, and compared with NM and NS.

2 Two classical iterative methods

In order to provide a theoretical basis for the filtering algorithm in Section 3, this

section introduces some properties of the two classical iterative algorithms. The most

widely used and best-known method is the Newton’s Method (NM):

( )

k kk

−

=+=X XX XA

, (1.1)

which can be derived in terms of

2=XI

. The NM is globally converged and has

quadratic convergence. One way to try to remove the inverse in the formula (1.1) is to

approximate it by one step of Newton’s method for the matrix inverse and we get the

Newton–Schulz Method (NS):

( )

13,

kkk+=−=X X IX X A

which is multiplication-rich and retains the quadratic convergence of Newton’s method.

However, it is locally convergent. Only when

21−<IA

, the iterative convergence can

be guaranteed [13]. Next, a residual recurrence formula is introduced.

Lemma 2.1.1 The residual terms

= −R IX

of NM and NS satisfies

( )

1 11 , 1, 2,

4 44

kk k

−

+= +− − =R R I IR 

, (1.2)

and

, 1, 2,

kkk

++= =RRR 

, (1.3)

respectively. If

( )

, Eq.(1.2) can be rewritten as

( )

k kk

−

=−−R RIR

Proof. Substituting Eq. (1.1) into

11kk++

= −R IX

( )

1 11

4 24

11 1

24 4

1 11 1

2 44 4

1 11 .

4 44

kk k

kkk

k kk

−

=− −−

=+−

= +− −

R IX IX

RX X

R IR X

R I IR

(1.4)

( )

, substituting

( )

k kk

−

− =+++IR IR R 

into Eq.(1.4) yields

( )

1 11

4 44

1 11 ...

4 44

kk k

k kk

−

= +− −

= + − +++

=−−

R R I IR

R I IR R

RIR

(1.5)

The residual term

= −R IX

of NS has the following relationship:

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

TwoIterativealgorithmsforthematrixsignfunctionbasedontheadaptivefilteringtechnologyFengWu*[1],KeqiYe[2],LiZhu[2],YuelingZhao[3],JiqiangHu[3]andWanxieZhong[3][1]SchoolofMathematicalSciences,StateKeyLaboratoryofStructuralAnalysisofIndustrialEquipment,FacultyofVehicleEngineeringandMechanics,DalianUnive...

展开>> 收起<<

Two Iterative algorithms for the matrix sign function based on the adaptive filtering technology Feng Wu1 Keqi Ye 2 Li Zhu 2 Yueling Zhao 3 Jiqiang Hu 3 and Wanxie Zhong 3.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Two Iterative algorithms for the matrix sign function based on the adaptive filtering technology Feng Wu1 Keqi Ye 2 Li Zhu 2 Yueling Zhao 3 Jiqiang Hu 3 and Wanxie Zhong 3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: