# A Fast Algorithm of Moore-Penrose Inverse for the Loewner-Type Matrix

Authors: QiuJuan Tong; SanYang Liu; Quan Lu
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

In this paper, we present a fast algorithm of Moore-Penrose inverse form×n Loewner-type matrix with full column rank by forming a special block matrix and studying its inverse. Its computation complexity is O(mn)+O(n2), but it is O(mn2)+O(n3) by using L+=(LTL)−1LT.


---

## Body

## 1. Introduction

Loewner matrix was first studied by Loewner in 1934 in [1]. He studied the relations of various Loewner matrices via the characteristic of the monotone matrix function and the problem of rational interpolation at that time. Since then, more further studies had been carried out by many scientists in [2–5], such as Belevitch, Donoghue Jr., Fiedler, Chen and Zhang. From their mentioned works, we can find various properties of Loewner matrix and its application in the rational interpolation. In 1984, Vavřín presented a fast algorithm for the inverse of Loewner matrix in [6], then the fast algorithm for the Loewner system was got accordingly. Rost and Vavřín presented a fast algorithm for the system whose coefficient is a Loewner-Vandermonde matrix from 1995 to 1996 in [7, 8]. Lu gave a fast triangular factorization algorithm for the symmetrical Loewner-type matrix in 2003 in [9]. Xu et al. and so forth gave a fast triangular factorization algorithm for the inverse of symmetrical Loewner-type matrix in 2003 in [10]. In 2009, Tong et al. gave a fast algorithm of the Moore-Penrose inverse for m×n symmetrical Loewner-type matrix [11]. In this paper, we generalize the fast algorithm of symmetrical Loewner-type matrix to the Loewner-type matrix. The theory and computation of generalized inverse matrix arise in various applications such as optimization theory, control theory, computation mathematics, and mathematical statistics. Therefore, there are very important theoretical and practical significance when we study the fast algorithm of Moore-Penrose inverse for the Loewner-type matrix.This paper is organized as follows: in Section1, we present some preliminaries results. The fast algorithm of Moore-Penrose inverse for Loewner-type matrix is driven in Section 2. We give some numerical examples to illustrate the fast algorithm obtained in Section 3.


## 2. Preliminaries

A Loewner matrixL1 is a matrix of the form L1=(lij)m×n=((ξi-ηj)/(αi-βj))i,j=1m,n, where αi,βj,ξi,andηj (i=1,2,…,m;j=1,2,…,n) are given numbers and αi≠βj. A Loewner-type matrix L is a matrix which satisfies (2.1)D̃L-LD=∑j=1lp(j)q(j)T,
where D̃=diag(α1,α2,…,αm),D=diag(β1,β2,…,βn), p(j)=(p1(j),p2(j),…,pm(j))T, and q(j)=(q1(j),q2(j),…,qn(j))T. Loewner matrix L1 is a special case of Loewner-type matrix, and it satisfies D̃L1-L1D=(ξ1,…,ξm)T(1,…,1)-(1,…,1)T(η1,…,ηn).Letn be the rank of m×n Loewner-type matrix L. Forming an m+n matrix (2.2)M=(-ImLLT0),
we obtain(2.3)M-1=(L(LTL)-1LT-ImL(LTL)-1(LTL)-1LT(LTL)-1)=(LL+-Im(LT)+L+(LTL)-1).It is obvious that we may obtain the Moore-Penrose inverseL+ of Loewner-type matrix L by (2.3) if we can get M-1.Now let us begin to findM-1.The following result will be useful for gettingM-1.Lemma 2.1 (see [12]).
Let all the leading principal submatricesSi(i=1,2,…,n) of matrix S=(sij)n×n whose order is n be invertible. Linear system Sx=b be given, where b=(b1,b2,…,bn)T. Note that bi=(b1,b2,…,bi)T, and let xi=(xi1,xi2,…,xii)T, ui=(u1i,u2i,…,uii)T be solution vectors of linear systems Sixi=bi, Siui=ei(i) differently, then
(2.4)xi=(xi-10)+σiui,
where σi=bi-∑j=1i-1sijxi-1,j.


## 3. Fast Algorithm of the Moore-Penrose Inverse for Loewner-Type Matrix

By using (2.1), we know that M satisfies (3.1)(D̃D)M-M(D̃D)=∑j=1l[(p(j)0n)(0mTq(j)T)-(0mq(j))(p(j)T0nT)].Let all the leading principal submatricesMi  (i=1,2,…,m+n) of M be invertible. If i>m, by virtue of (3.1), we have(3.2)(D̃Di-m)Mi-Mi(D̃Di-m)=∑j=1l[(p(j)0i-m)(0mTqi-m(j)T)-(0mqi-m(j))(p(j)T0i-mT)].Letgi(j)=(gi1(j),gi2(j),…,gii(j))T, hi(j)=(hi1(j),hi2(j),…,hii(j))T be solution vectors of linear systems (3.3)Migi(j)=(p(j)0i-m),Mihi(j)=(0mqi-m(j))(i=m,m+1,…,m+n)
differently, then using Mm=-Im, we obtain gm(j)=-p(j), hm(j)=0m. By virtue of Lemma 2.1 we have (3.4)gi(j)=(gi-1(j)0)+σi(j)ui,hi(j)=(hi-1(j)0)+τi(j)ui,
where σi(j)=-∑k=1mlk,i-mgi-1,k(j), τi(j)=qi-m(j)-∑k=1mlk,i-mhi-1,k(j), and ui=(u1i,u2i,…,uii)T is a solution vector of Miui=ei(i). Multiplying (3.2) by Mi-1 on the left and on the right differently, we obtain(3.5)Mi-1(D̃Di-m)-(D̃Di-m)Mi-1=∑j=1l(gi(j)hi(j)T-hi(j)gi(j)T).
Multiplying (3.5) by ei(i) and noting that (D̃Di-m)ei(i)=βi-mei(i), we have (3.6)βi-mui-(D̃Di-m)ui=∑j=1l(hii(j)gi(j)-gii(j)hi(j)).
Substituting (3.4) in (3.6) and noting that gii(j)=σi(j)uii, hii(j)=τi(j)uii, we have(3.7)βi-mui-(D̃Di-m)ui=uii∑j=1l(τi(j)(gi-1(j)0)-σi(j)(hi-1(j)0)),
and hence, (3.8)uki={uii∑j=1l(τi(j)gi-1,k(j)-σi(j)hi-1,k(j))βi-m-αk(k=1,2,…,m),uii∑j=1l(τi(j)gi-1,k(j)-σi(j)hi-1,k(j))βi-m-βk-m(k=m+1,m+2,…,i-1).
Now, let us look for uii. Choosing the ith of Miui=ei(i), namely (3.9)∑k=1mlk,i-muki,
and using (3.8), we have (3.10)uii=1∑k=1mlk,i-m/(βi-m-αk)[∑j=1l(τi(j)gi-1,k(j)-σi(j)hi-1,k(j))].Note thatM-1=(v1,v2,…,vm+n), where vi=(v1i,v2i,…,vm+n,i)T is the ith column of M-1, then (3.11)vm+n=um+n.
Letting i=m+n in (3.5) and multiplying it by ek(m+n)(k>m) on the right, we have(3.12)βk-mvk-(D̃D)vk=∑j=1l(hm+n,k(j)gm+n(j)-gm+n,k(j)hm+n(j)).So, we obtain the fast algorithm of Moore-Penrose inverseL+ of Loewner-type matrix L by (2.3), (3.4), and (3.8)~(3.12).Algorithm
Step 1.
(3.13)gm(j)=-p(j),hm(j)=0m(j=1,2,…,l),
Fori=m+1,m+2,…,m+n,
(3.14)σi(j)=-∑k=1mlk,i-mgi-1,k(j),τi(j)=qi-m(j)-∑k=1mlk,i-mhi-1,k(j)(j=1,2,…,l),tik=∑j=1l(τi(j)gi-1,k(j)-σi(j)hi-1,k(j))(k=1,2,…,i-1),λi=∑k=1mlk,i-mβi-m-αktik,uii=1λi,uki=uiiβi-m-αktik(k=1,2,…,m),uki=uiiβi-m-βk-mtik(k=m+1,m+2,…,i-1),gi(j)=(gi-1(j)0)+σi(j)ui,hi(j)=(hi-1(j)0)+τi(j)ui(j=1,2,…,l).Step 2.
(3.15)vi,m+n=ui,m+n(i=1,2,…,m).
Fork=m+1,…m+n-1,
(3.16)vik=1βk-m-αi∑j=1l(gm+n,i(j)hm+n,k(j)-hm+n,i(j)gm+n,k(j))(i=1,…,m),
then
(3.17)L+=(v1,m+1⋯vm,m+1⋮⋮v1,m+n⋯vm,m+n).
The algorithm requires(7l-3)mn+ln2+O(m) multiplication and division operations and (5l-3)mn+(l/2)n2+O(m) addition and subtraction operations, and the computation complexity is O(mn)+O(n2), but it is O(mn2)+O(n3) by using L+=(LTL)-1LT.


## 4. Numerical Examples

We get the Moore-Penrose inverse matrix of Loewner-type matrix with Fortran program in computer, and the results of the partial numerical examples are given as follows in Table1 (the error is measured by the 2-norm of vector, and the time is measured by second).Table 1Orders of matrixFast algorithmL+=(LTL)-1LTmnErr.Tim.Err.Tim.10000207.254e−1628.109e−141120000202.398e−1522.788e−143130000202.019e−1552.106e−148940000209.108e−1481.001e−1420160000204.901e−14363.760e−14705Example 1.
Consider(4.1)αi=(i-1)πm-n+1,βj=(j+1)πm+n-1,ξi=(-1)i(i-mn),ηj=jj-m.p(1)(i)=ξi2,p(2)(i)=1,p(3)(i)=ξi2,p(4)(i)=1;q(1)(j)=1,q(2)(j)=-ηj,q(3)(j)=1,q(4)(j)=-ηj.i=1,2,…,m;j=1,2,…,n.From above examples and many more examples not given, we find that the stability of the fast algorithm is very good, and it needs shorter time than that ofL+=(LTL)-1LT.



---

*Source: 301971-2012-01-04.xml*