GeneralBrokenLines V03-01-02
gblpy
gblnum.py
Go to the documentation of this file.
1'''
2Algebra for linear equation system with bordered band matrix.
3
4Created on Jul 27, 2011
5
6@author: kleinwrt
7'''
8
9## \file
10# Bordered band matrix.
11#
12# \author Claus Kleinwort, DESY, 2011 (Claus.Kleinwort@desy.de)
13#
14# \copyright
15# Copyright (c) 2011 - 2023 Deutsches Elektronen-Synchroton,
16# Member of the Helmholtz Association, (DESY), HAMBURG, GERMANY \n\n
17# This library is free software; you can redistribute it and/or modify
18# it under the terms of the GNU Library General Public License as
19# published by the Free Software Foundation; either version 2 of the
20# License, or (at your option) any later version. \n\n
21# This library is distributed in the hope that it will be useful,
22# but WITHOUT ANY WARRANTY; without even the implied warranty of
23# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24# GNU Library General Public License for more details. \n\n
25# You should have received a copy of the GNU Library General Public
26# License along with this program (see the file COPYING.LIB for more
27# details); if not, write to the Free Software Foundation, Inc.,
28# 675 Mass Ave, Cambridge, MA 02139, USA.
29
30import numpy as np
31
32
33
65class BorderedBandMatrix(object):
66
67
73 def __init__(self, nSize, nBorder=1, nBand=7):
74 nSizeBand = nSize - nBorder
75
76 self.__numSize = nSize
77
78 self.__numBorder = nBorder
79
80 self.__numBand = 0 # actual band width
81
82 self.__numCol = nSizeBand
83
84 self.__border = np.zeros((nBorder, nBorder))
85
86 self.__mixed = np.zeros((nBorder, nSizeBand))
87
88 self.__band = np.zeros((nBand + 1, nSizeBand))
89# print " new BBM ", self.__border__.shape, self.__mixed__.shape, self.__band__.shape
90
91
98 def addBlockMatrix(self, aIndex, aMatrix):
99 nBorder = self.__numBorder
100 for i in range(len(aIndex)):
101 iIndex = aIndex[i] - 1
102 for j in range(i + 1):
103 jIndex = aIndex[j] - 1
104 if (iIndex < nBorder):
105 self.__border[iIndex, jIndex] += aMatrix[i, j]
106 if (iIndex != jIndex):
107 self.__border[jIndex, iIndex] += aMatrix[i, j]
108 elif (jIndex < nBorder):
109 self.__mixed[jIndex, iIndex - nBorder] += aMatrix[i, j]
110 else:
111 nBand = iIndex - jIndex
112 self.__band[nBand, jIndex - nBorder] += aMatrix[i, j]
113
114 self.__numBand = max(self.__numBand, nBand)
115 return self.__numBand
116
117
124 def getBlockMatrix(self, aIndex):
125 nBorder = self.__numBorder
126 nBand = self.__numBand
127 nSize = len(aIndex)
128 aMatrix = np.empty((nSize, nSize))
129 for i in range(nSize):
130 iIndex = aIndex[i] - 1
131 for j in range(i + 1):
132 jIndex = aIndex[j] - 1
133 iMax = max(iIndex, jIndex)
134 iMin = min(iIndex, jIndex)
135 if (iMax < nBorder):
136 aMatrix[i, j] = self.__border[iIndex, jIndex]
137 elif (iMin < nBorder):
138 aMatrix[i, j] = self.__mixed[iMin, iMax - nBorder]
139 else:
140 iBand = iMax - iMin
141 if iBand <= nBand:
142 aMatrix[i, j] = self.__band[iBand, iMin - nBorder]
143 else:
144 aMatrix[i, j] = 0.
145 aMatrix[j, i] = aMatrix[i, j]
146 return aMatrix
147
148
152 def getBandCond(self):
153 diagMax = np.max(self.__band[0])
154 diagMin = np.min(self.__band[0])
155 return diagMax/diagMin if diagMin > 0. else 0.
156
157
159 def printMatrix(self):
160 print " block part "
161 nRow = self.__numBorder
162 for i in range(nRow):
163 print " row ", i, self.__border[i]
164 print " mixed part "
165 for i in range(nRow):
166 print " row ", i, self.__mixed[i]
167 nRow = self.__numBand + 1
168 print " band part "
169 for i in range(nRow):
170 print " diagonal ", i, self.__band[i]
171
172
179 def solveAndInvertBorderedBand(self, aRightHandSide):
180
181#============================================================================
182
189 nRow = self.__numBand + 1
190 nCol = self.__numCol
191 auxVec = np.copy(self.__band[0]) * 16.0 # save diagonal elements
192 for i in range(nCol):
193 if ((self.__band[0, i] + auxVec[i]) != self.__band[0, i]):
194 self.__band[0, i] = 1.0 / self.__band[0, i]
195 else:
196 self.__band[0, i] = 0.0 # singular
197 for j in range(min(nRow, nCol - i) - 1):
198 rxw = self.__band[j + 1, i] * self.__band[0, i]
199 for k in range(min(nRow, nCol - i) - j - 1):
200 self.__band[k, i + j + 1] -= self.__band[k + j + 1, i] * rxw
201 self.__band[j + 1, i] = rxw
202
203
208 def solveBand(aRightHandSide):
209 nRow = self.__numBand + 1
210 nCol = self.__numCol
211 aSolution = np.copy(aRightHandSide)
212 for i in range(nCol): # forward substitution
213 for j in range(min(nRow, nCol - i) - 1):
214 aSolution[j + i + 1] -= self.__band[j + 1, i] * aSolution[i]
215 for i in range(nCol - 1, -1, -1): # backward substitution
216 rxw = self.__band[0, i] * aSolution[i]
217 for j in range(min(nRow, nCol - i) - 1):
218 rxw -= self.__band[j + 1, i] * aSolution[j + i + 1]
219 aSolution[i] = rxw
220 return aSolution
221
222
227 nRow = self.__numBand + 1
228 nCol = self.__numCol
229 inverseBand = np.zeros((nRow, nCol))
230 for i in range(nCol - 1, -1, -1):
231 rxw = self.__band[0, i]
232 for j in range(i, max(0, i - nRow + 1) - 1, -1):
233 for k in range(j + 1, min(nCol, j + nRow)):
234 rxw -= inverseBand[abs(i - k), min(i, k)] * self.__band[k - j, j]
235 inverseBand[i - j, j] = rxw
236 rxw = 0.0
237 return inverseBand
238
239
245 def bandOfAVAT(anArray, aSymArray):
246 nCol = self.__numCol
247 nBand = self.__numBand
248 aBand = np.empty((nBand + 1, nCol))
249 for i in range(nCol):
250 for j in range(max(0, i - nBand), i + 1):
251 aBand[i - j, j] = np.dot(anArray[i], np.dot(aSymArray, anArray[j]))
252 return aBand
253
254# setup
255 nBorder = self.__numBorder
256# nRow = self.__numBand +1
257 nCol = self.__numCol
258 aSolution = np.empty(nBorder + nCol)
259# decompose band
261 if ((self.__band[0] <= 0.0).any()):
262 raise ZeroDivisionError("Band matrix not positive definite")
263
264 if (nBorder > 0):
265 auxMat = np.empty((nBorder, nCol))
266# solve for mixed part
267 for i in range(nBorder):
268 auxMat[i] = solveBand(self.__mixed[i])
269 auxMatT = auxMat.T
270# solve for border
271 auxVec = aRightHandSide[:nBorder] - np.dot(auxMat, aRightHandSide[nBorder:])
272 invBorder = np.linalg.inv(self.__border - np.dot(self.__mixed, auxMatT))
273 aSolution[:nBorder] = np.dot(invBorder, auxVec)
274# solve for band part
275 aSolution[nBorder:] = solveBand(aRightHandSide[nBorder:]) \
276 -np.dot(auxMatT, aSolution[:nBorder])
277# parts of inverse
278 self.__border = invBorder
279 self.__mixed = np.dot(-invBorder, auxMat)
280 self.__band = invertBand() + bandOfAVAT(auxMatT, invBorder)
281 else:
282# solve for band part (only)
283 aSolution = solveBand(aRightHandSide)
284 self.__band = invertBand()
285 return aSolution
(Symmetric) Bordered Band Matrix.
Definition: gblnum.py:65
def solveAndInvertBorderedBand(self, aRightHandSide)
Solve linear equation A*x=b system with BBmatrix A, calculate BB part of inverse of A.
Definition: gblnum.py:179
__numCol
size of band part of matrix; int
Definition: gblnum.py:82
__border
border part B; matrix(float)
Definition: gblnum.py:84
def addBlockMatrix(self, aIndex, aMatrix)
Add (compressed) block to BBmatrix:
Definition: gblnum.py:98
__numBorder
size of border; int
Definition: gblnum.py:78
__numBand
size of border; int
Definition: gblnum.py:80
def __init__(self, nSize, nBorder=1, nBand=7)
Create new BBmatrix.
Definition: gblnum.py:73
def getBandCond(self)
Get condition from band part decomposition.
Definition: gblnum.py:152
__band
band part C; matrix(float)
Definition: gblnum.py:88
__numSize
size of matrix; int
Definition: gblnum.py:76
def printMatrix(self)
Print BBmatrix.
Definition: gblnum.py:159
__mixed
mixed part M; matrix(float)
Definition: gblnum.py:86
def getBlockMatrix(self, aIndex)
Retrieve (compressed) block from BBmatrix:
Definition: gblnum.py:124
def decomposeBand()
Definition: gblnum.py:188
def invertBand()
Invert band part.
Definition: gblnum.py:226
def bandOfAVAT(anArray, aSymArray)
Calculate band part of A*V*A^T.
Definition: gblnum.py:245
def solveBand(aRightHandSide)
Solve linear equation system for band part.
Definition: gblnum.py:208