Bidiagonal Decompositions of Vandermonde-Type Matrices of Arbitrary Rank

2025-05-06 0 0 468.65KB 24 页 10玖币

侵权投诉

Bidiagonal Decompositions

of Vandermonde-Type Matrices of Arbitrary Rank?,??

Jorge Delgadoa, Plamen Koevb,∗

, Ana Marcoc, Jos´e-Javier Mart´ınezd, Juan

Manuel Pe˜nae, Per-Olof Perssonf, Steven Spasovg

aDepartamento de Matem´atica Aplicada, Universidad de Zaragoza, Ediﬁcio Torres

Quevedo, Zaragoza, 50019, Spain

bDepartment of Mathematics, San Jos´e State University, San Jose, 95192, U.S.A.

cDepartamento de F´ısica y Matem´aticas, Universidad de Alcal´a, Alcal´a de

Henares, Madrid, 28871, Spain

dDepartamento de F´ısica y Matem´aticas, Universidad de Alcal´a, Alcal´a de

Henares, Madrid, 28871, Spain

eDepartamento de Matem´atica Aplicada, Universidad de Zaragoza, Ediﬁcio de

Matem´aticas, Zaragoza, 50019, Spain

fDepartment of Mathematics, University of California, Berkeley, 94720, U.S.A.

gSoﬁa High School of Mathematics, 61 Iskar St., Soﬁa, 1000, Bulgaria

Abstract

We present a method to derive new explicit expressions for bidiagonal decom-

positions of Vandermonde and related matrices such as the (q-, h-) Bernstein-

Vandermonde ones, among others. These results generalize the existing ex-

pressions for nonsingular matrices to matrices of arbitrary rank. For totally

nonnegative matrices of the above classes, the new decompositions can be com-

puted eﬃciently and to high relative accuracy componentwise in ﬂoating point

arithmetic. In turn, matrix computations (e.g., eigenvalue computation) can

also be performed eﬃciently and to high relative accuracy.

Keywords: Vandermonde matrix, totally nonnegative matrix, bidiagonal

decomposition, eigenvalue

2000 MSC: 65F15, 15A23, 15B48, 15B35

?This research was partially supported by Spanish Research Grant PGC2018-096321-B-

I00(MCIU/AEI) and by Gobierno de Arag´on (E41-17R) . The authors A. Marco and J. J.

Mart´ınez are members of the Reseach Group asynacs (Ref. ct-ce2019/683) of Universidad

de Alcal´a.

?? This research was also partially supported by the Woodward Fund for Applied Mathemat-

ics at San Jos´e State University. The Woodward Fund is a gift from the estate of Mrs. Marie

Woodward in memory of her son, Henry Teynham Woodward. He was an alumnus of the

Mathematics Department at San Jos´e State University and worked with research groups at

NASA Ames.

∗Corresponding author

Email addresses: jorgedel@unizar.es (Jorge Delgado), plamen.koev@sjsu.edu (Plamen

Koev), ana.marco@uah.es (Ana Marco), jjavier.martinez@uah.es (Jos´e-Javier Mart´ınez),

jmpena@unizar.es (Juan Manuel Pe˜na), persson@berkeley.edu (Per-Olof Persson),

stevenspasov@gmail.com (Steven Spasov)

Preprint submitted to Journal of Computational and Applied Mathematics October 20, 2022

arXiv:2210.10148v1 [math.NA] 18 Oct 2022

1. Introduction

A matrix is totally nonnegative (TN) if all of its minors are nonnegative

[1, 2, 3]. The bidiagonal decompositions of the TN matrices have become an

important tool in the study of these matrices [4, 5] and for performing matrix

computations with them accurately and eﬃciently [6, 7, 8]. The bidiagonal

decompositions of many classical TN matrices such as Vandermonde and many

related matrices are well known, but contain singularities when some of the

nodes coincide. For example, a 3 ×3 Vandermonde matrix with nodes x, y, z is

decomposed as [6]:





1x x2

1y y2

1z z2

=



1 1 





1 1

z−y

y−x1





y−x

(z−x)(z−y)



×



1





1

.(1)

This decomposition is undeﬁned when x=y, which is unfortunate, since the

Vandermonde matrix is very well deﬁned for any values of the nodes.

By relaxing the requirement that the bidiagonal factors have ones on the

main diagonal, we show how to rearrange the factors in (1), so that the new

decomposition contains no singularities and is valid for any values of the nodes

and is thus valid for a Vandermonde matrix of arbitrary rank. For example, the

3×3 Vandermonde from (1) can be decomposed as





1x x2

1y y2

1z z2

=



1z−y





1y−x

1z−x





1



×



1





1

,(2)

which is valid for any values of the nodes x, y, z.

Many classes of other TN matrices share the exact same singularities in their

bidiagonal decompositions, e.g., the Bernstein-Vandermonde, their q-, h-, and

rational generalizations, Lupa¸s, Said-Ball matrices, etc. [6, 9, 10, 11, 12, 13, 14,

15, 16]. We call these matrices Vandermonde-type below (see section 3).

The method that allowed us to obtain the decomposition (2) from (1) applies

to all Vandermonde-type matrices (section 5) and is the main contribution of

this paper. The starting point for our method is the existing bidiagonal decom-

positions of the Vandermonde-type matrices, which are valid only when these

matrices are both TN and nonsingular. Our method takes these decompositions

as a starting point and produces new bidiagonal decompositions valid for matri-

ces of arbitrary rank, regardless of whether they are TN or not – see Corollary

4.1.

While the computational complexity of the transformed bidiagonal decom-

position of an n×nmatrix remains O(n2), the new expressions are simpler.

In terms of accuracy, just like their non-singular counterparts, the new de-

compositions remain insusceptible to subtractive cancellation, and thus all of

the entries of these decompositions can be computed to high relative accuracy

when the matrix is TN. By “high relative accuracy” we mean that for each

entry its sign and most of its leading signiﬁcant digits are computed correctly

(see section 8).

The Vandermonde-type matrices have many applications that are well ref-

erenced in the papers we cite above that deal with the nonsingular case. For

example, the Lupa¸s matrices (section 10.1) have direct applications in CAGD

[11, 17]. For TN Vandermonde-type matrices, the new results in this paper allow

for matrix computations with them to be performed to high relative accuracy

very eﬃciently (in O(n3) time) using the methods of [8] now also when these

matrices are singular – see section 9 for a numerical example.

The eﬃciency and high relative accuracy is particularly relevant, for exam-

ple, in eigenvalue computations since the corresponding matrices are unsym-

metric. The error bounds for the eigenvalues computed by the conventional

algorithms (such as the ones in LAPACK [18]) [19] imply that none of the

eigenvalues are guaranteed to be accurate, although the largest ones typically

are – see the example in section 9. In contrast, the results of this paper now

allow for all eigenvalues to be eﬃciently computed to high relative accuracy and,

in particular, the zero eigenvalues are computed exactly.

The paper is organized as follows. In section 2 we review the bidiagonal

decompositions of nonsingular TN matrices. In section 3 we present the formal

deﬁnition of Vandermonde-type matrix and, in section 4, we show how to re-

move the singularities in its bidiagonal decomposition. We demonstrate how our

method applies to the particular class of q-Bernstein-Vandermonde matrices in

section 5. Our method is also directly applicable to derivative matrices, such as

generalized Vandermonde matrices, Laguerre matrices, etc., which are subma-

trices or products of Vandermonde matrices and other nonsingular TN matrices

(section 6). In section 7, we present a method to make the bottom right-hand

corner entry of all bidiagonal factors in the corresponding bidiagonal decompo-

sitions equal to 1 – this is a requirement for the methods of [8] to work. We

discuss accuracy issues in section 8 and present numerical experiments in section

9. The explicit formulas for the decompositions of several Vandermonde-type

matrices are in the Appendix.

2. Bidiagonal decompositions of TN matrices

Our focus in this paper is on the class of TN matrices, but the formulas and

methods we present are valid without the requirement of total nonnegativity

(Corollary 4.1 below). The bidiagonal decompositions of the TN matrices serve

as a major tool in their study and computations with them. We review those

here [2, 4].

A nonsingular n×nTN matrix Acan be uniquely factored as

A=L(1)L(2) · · · L(n−1)DU(n−1)U(n−2) · · · U(1),(3)

where L(i)are n×nnonnegative and unit lower bidiagonal, Dis n×nnonneg-

ative and diagonal, and U(i)are n×nnonnegative and unit upper bidiagonal.

For the nontrivial entries of the factors L(k)and U(k), respectively, we have

L(k)

i+1,i =U(k)

i,i+1 = 0 for i<n−k.

We call the above decomposition (3), the ordinary bidiagonal decomposition

of Ato distinguish it from what we will deﬁne below as the singularity-free

bidiagonal decomposition of a TN matrix.

The decomposition (3) occurs naturally in the process of complete Neville

elimination when adjacent rows and columns are used for elimination [4, 5].

There are exactly n2nontrivial entries which parameterize the ordinary bidi-

agonal decomposition (3). Following [6, sec. 4], those nontrivial entries can be

conveniently stored in an n×nmatrix M, denoted M=BD(A), where:

mij =L(n−i+j)

i,i−1, i > j,

mij =U(n−j+i)

j−1,j , i < j, (4)

mii =Dii.

Namely, for k= 1,2, . . . , n −1,

L(k)=







...

mn−k+1,11

mn−k+2,21

......

mnk 1







U(k)=







...

1m1,n−k+1

1m2,n−k+2

......

1mnk







and

D= diag(m11, m22, . . . , mnn).

For i6=j, the mij are the multipliers of the complete Neville elimination

with which the (i, j) entry of Ais eliminated and mii are the diagonal entries

of D.

For example, if Ais the 3×3 Vandermonde matrix from (1), then the matrix

M=BD(A) is:

M=



1x x

1y−x y

1z−y

y−x(z−x)(z−y)

.(5)

In this paper, we assume that explicit expressions for the entries of the

ordinary bidiagonal decomposition (3) are given. For the matrices we consider

in this paper, those expressions contain singularities when some of the nodes

coincide and we work to remove those singularities.

To that end, we drop the requirement that the matrices L(i)and U(i)have

ones on the main diagonal. We deﬁne a new bidiagonal decomposition, which

we call singularity-free bidiagonal decomposition and denote it by SBD(A), as

A=L1L2· · · Ln−1DUn−1Un−2· · · U1.(6)

The matrix Dis nonnegative and diagonal. The factors Liand Uiare nonneg-

ative lower and upper bidiagonal, and have the same nonzero patterns as L(i)

and U(i), respectively, i= 1,2, . . . , n −1. Namely, (Lk)i+1,i = (Uk)i,i+1 = 0 for

i<n−k(see theorem 2.1 in [6]).

Following [8], the nontrivial entries of SBD(A) are stored in two matrices:

B, which is n×nand C, which is (n+ 1) ×(n+ 1):

[B, C] = SBD(A).

As with BD(A), the matrix Bstores the nontrivial oﬀdiagonal entries of Liand

Uias well as the diagonal entries of D, exactly as in (4):

bij = (Ln−i+j)i,i−1, i > j,

bij = (Un−j+i)j−1,j , i < j,

bii =Dii.

The matrix Cstores the diagonal entries of Liand Uias

cij =(Ln−i+j)i−1,i−1, i > j,

(Un−j+i)j−1,j−1, i < j.

In this arrangement, cij , i > j, is the diagonal entry in Ln−i+jimmediately

above bij and similarly for i<jand Un−j+i. The entries cii, i = 1,2, . . . , n + 1

as well as the entries c1,n+1 and cn+1,1are unused. This is the same construction

as the one given in formula (9) in [8], except that we now allow for the (n, n)

entry in Liand Uito be any nonnegative number and not necessarily equal 1.

This is the reason we need an (n+ 1) ×(n+ 1) matrix to host the entries cij :

the nontrivial diagonal entries of L1, L2, . . . , Ln−1are of lengths 2,3, . . . , n, and

similarly for the Ui’s.

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

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

10 玖币 0人已下载

立即下载

摘要：

BidiagonalDecompositionsofVandermonde-TypeMatricesofArbitraryRank?;??JorgeDelgadoa,PlamenKoevb,,AnaMarcoc,Jose-JavierMartnezd,JuanManuelPe~nae,Per-OlofPerssonf,StevenSpasovgaDepartamentodeMatematicaAplicada,UniversidaddeZaragoza,EdicioTorresQuevedo,Zaragoza,50019,SpainbDepartmentofMathematics,...

展开>> 收起<<

Bidiagonal Decompositions of Vandermonde-Type Matrices of Arbitrary Rank.pdf

共24页,预览5页

还剩页未读，继续阅读

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

Bidiagonal Decompositions of Vandermonde-Type Matrices of Arbitrary Rank

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: