Graph centers used for stabilization of matrix factorizations

Pavla Kabelíková

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 2, page 249-259
  • ISSN: 2083-5892

Abstract

top
Systems of consistent linear equations with symmetric positive semidefinite matrices arise naturally while solving many scientific and engineering problems. In case of a "floating" static structure, the boundary conditions are not sufficient to prevent its rigid body motions. Traditional solvers based on Cholesky decomposition can be adapted to these systems by recognition of zero rows or columns and also by setting up a well conditioned regular submatrix of the problem that is used for implementation of a generalised inverse. Conditioning such a submatrix seems to be related with detection of so called fixing nodes such that the related boundary conditions make the structure as stiff as possible. We can consider the matrix of the problem as an unweighted non-oriented graph. Now we search for nodes that stabilize the solution well-fixing nodes (such nodes are sufficiently far away from each other and are not placed near any straight line). The set of such nodes corresponds to one type of graph center.

How to cite

top

Pavla Kabelíková. "Graph centers used for stabilization of matrix factorizations." Discussiones Mathematicae Graph Theory 30.2 (2010): 249-259. <http://eudml.org/doc/271029>.

@article{PavlaKabelíková2010,
abstract = { Systems of consistent linear equations with symmetric positive semidefinite matrices arise naturally while solving many scientific and engineering problems. In case of a "floating" static structure, the boundary conditions are not sufficient to prevent its rigid body motions. Traditional solvers based on Cholesky decomposition can be adapted to these systems by recognition of zero rows or columns and also by setting up a well conditioned regular submatrix of the problem that is used for implementation of a generalised inverse. Conditioning such a submatrix seems to be related with detection of so called fixing nodes such that the related boundary conditions make the structure as stiff as possible. We can consider the matrix of the problem as an unweighted non-oriented graph. Now we search for nodes that stabilize the solution well-fixing nodes (such nodes are sufficiently far away from each other and are not placed near any straight line). The set of such nodes corresponds to one type of graph center. },
author = {Pavla Kabelíková},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {FETI; parallel computing; generalised inverse; graph center},
language = {eng},
number = {2},
pages = {249-259},
title = {Graph centers used for stabilization of matrix factorizations},
url = {http://eudml.org/doc/271029},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Pavla Kabelíková
TI - Graph centers used for stabilization of matrix factorizations
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 2
SP - 249
EP - 259
AB - Systems of consistent linear equations with symmetric positive semidefinite matrices arise naturally while solving many scientific and engineering problems. In case of a "floating" static structure, the boundary conditions are not sufficient to prevent its rigid body motions. Traditional solvers based on Cholesky decomposition can be adapted to these systems by recognition of zero rows or columns and also by setting up a well conditioned regular submatrix of the problem that is used for implementation of a generalised inverse. Conditioning such a submatrix seems to be related with detection of so called fixing nodes such that the related boundary conditions make the structure as stiff as possible. We can consider the matrix of the problem as an unweighted non-oriented graph. Now we search for nodes that stabilize the solution well-fixing nodes (such nodes are sufficiently far away from each other and are not placed near any straight line). The set of such nodes corresponds to one type of graph center.
LA - eng
KW - FETI; parallel computing; generalised inverse; graph center
UR - http://eudml.org/doc/271029
ER -

References

top
  1. [1] O. Axelsson, Iterative Solution Methods (Cambridge University Press: Cambridge, 1994). Zbl0795.65014
  2. [2] T. Brzobohatý, Z. Dostál, T. Kozubek and A. Markopoulos, Combining Cholesky decomposition with SVD to stable evaluation of a generalised inverse of the stiffness matrix of a floating structure, submited, 2009. Zbl1242.74235
  3. [3] Z. Dostál, D. Horák, R. Kucera, V. Vondrák, J. Haslinger, J. Dobiás and S. Pták, FETI based algorithms for contact problems: scalability, large displacements and 3D Coulomb friction, Computer Methods in Applied Mechanics and Engineering 194 (2005) 395-409, doi: 10.1016/j.cma.2004.05.015. Zbl1085.74046
  4. [4] Z. Dostál, D. Horák and R. Kucera, Total FETI - an easier implementable variant of the FETI method for numerical solution of elliptic PDE, Communications in Numerical Methods in Engineering 22 (2006) 1155-1162, doi: 10.1002/cnm.881. Zbl1107.65104
  5. [5] C. Farhat and M. Géradin, On the general solution by a direct method of a large scale singular system of linear equations: application to the analysis of floating structures, Int. J. Numer. Meth. Engng 41 (1998) 675-696, doi: 10.1002/(SICI)1097-0207(19980228)41:4<675::AID-NME305>3.0.CO;2-8 
  6. [6] C. Farhat and F.-X. Roux, A method of finite element tearing and interconnecting and its parallel solution algorithm, Int. J. Numer. Meth. Engng 32 (1991) 1205-1227, doi: 10.1002/nme.1620320604. Zbl0758.65075
  7. [7] Ch. Godsil and G. Royle, Algebraic Graph Theory (Springer-Verlag, New York, ISBN 0-387-95241-1, 2001). Zbl0968.05002
  8. [8] G.H. Golub and C.F. Van Loan, Matrix Computations (2nd ed.) (John Hopkins University Press, Baltimore, 1989). Zbl0733.65016
  9. [9] P. Kabelíková, T. Kozubek, A. Markopoulos and T. Brzobohatý, Effective Algorithms for Implementation of FETI-Based Domain Decomposition Methods, submited, 2009. 
  10. [10] G. Karypis and V. Kumar, METIS manual Version 4.0, [online] http://glaros.dtc.umn.edu/gkhome/views/metis, University of Minnesota, 1998. 
  11. [11] C.T. Pan, On the existence and factorization of rank-revealing LU factorizations, Linear Algebra and Its Applications 316 (2000) 199-222, doi: 10.1016/S0024-3795(00)00120-8. Zbl0962.65023
  12. [12] M. Papadrakakis and Y. Fragakis, An integrated geometric-algebraic method for solving semi-definite problems in structural mechanics, Computer Methods in Applied Mechanics and Engineering 190 (2001) 6513-6532, doi: 10.1016/S0045-7825(01)00234-1. 
  13. [13] K.C. Park and C.A. Felipa, The construction of free-free flexibility matrices for multilevel structural analysis, Int. J. Numer. Meth. Engng 47 (2000) 395-418, doi: 10.1002/(SICI)1097-0207(20000110/30)47:1/3<395::AID-NME777>3.3.CO;2-0 
  14. [14] K.C. Park, C.A. Felipa and U.A. Gumaste, A localized version of the method of Lagrange multipliers, Computational Mechanics 24 (2000) 476-490, doi: 10.1007/s004660050007. Zbl0961.74077

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.