Fault tolerant matrix triangularization and solution of linear systems of equations

Patrick Fitzpatrick; Colin C. Murphy

Fault tolerant matrix triangularization and solution of linear systems of equations

Patrick Fitzpatrick
, Colin C. Murphy

School of Engineering and Architecture

University College Cork

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

Abstract

We present a fault tolerant algorithm for the solution of linear systems of equations using matrix triangularization procedures suitable for implementation on array architectures. Gaussian elimination with partial or pairwise pivoting and QR decomposition are made fault tolerant against two transient errors occurring during the triangularization procedure. The extended Euclidean algorithm is implemented to solve for the locations and values of the errors defined appropriately using the theory of error correcting codes. The Sherman-Morrison-Woodbury formula is then used to obtain the correct solution vector to the linear system of equations without requiring a valid decomposition.

Original language	English
Title of host publication	Proceedings of the International Conference on Application
Publisher	Publ by IEEE
Pages	469-480
Number of pages	12
ISBN (Print)	0818629673
Publication status	Published - 1992
Event	Proceedings of the International Conference on Application Specific Array Processors - Berkeley, CA, USA Duration: 4 Aug 1992 → 7 Aug 1992

Publication series

Name	Proceedings of the International Conference on Application

Conference

Conference	Proceedings of the International Conference on Application Specific Array Processors
City	Berkeley, CA, USA
Period	4/08/92 → 7/08/92

Cite this

@inbook{42d6bedb447840a585f9039fd64cd761,

title = "Fault tolerant matrix triangularization and solution of linear systems of equations",

abstract = "We present a fault tolerant algorithm for the solution of linear systems of equations using matrix triangularization procedures suitable for implementation on array architectures. Gaussian elimination with partial or pairwise pivoting and QR decomposition are made fault tolerant against two transient errors occurring during the triangularization procedure. The extended Euclidean algorithm is implemented to solve for the locations and values of the errors defined appropriately using the theory of error correcting codes. The Sherman-Morrison-Woodbury formula is then used to obtain the correct solution vector to the linear system of equations without requiring a valid decomposition.",

author = "Patrick Fitzpatrick and Murphy, \{Colin C.\}",

year = "1992",

language = "English",

isbn = "0818629673",

series = "Proceedings of the International Conference on Application",

publisher = "Publ by IEEE",

pages = "469--480",

booktitle = "Proceedings of the International Conference on Application",

note = "Proceedings of the International Conference on Application Specific Array Processors ; Conference date: 04-08-1992 Through 07-08-1992",

}

Fitzpatrick, P & Murphy, CC 1992, Fault tolerant matrix triangularization and solution of linear systems of equations. in Proceedings of the International Conference on Application. Proceedings of the International Conference on Application, Publ by IEEE, pp. 469-480, Proceedings of the International Conference on Application Specific Array Processors, Berkeley, CA, USA, 4/08/92.

TY - CHAP

T1 - Fault tolerant matrix triangularization and solution of linear systems of equations

AU - Fitzpatrick, Patrick

AU - Murphy, Colin C.

PY - 1992

Y1 - 1992

N2 - We present a fault tolerant algorithm for the solution of linear systems of equations using matrix triangularization procedures suitable for implementation on array architectures. Gaussian elimination with partial or pairwise pivoting and QR decomposition are made fault tolerant against two transient errors occurring during the triangularization procedure. The extended Euclidean algorithm is implemented to solve for the locations and values of the errors defined appropriately using the theory of error correcting codes. The Sherman-Morrison-Woodbury formula is then used to obtain the correct solution vector to the linear system of equations without requiring a valid decomposition.

AB - We present a fault tolerant algorithm for the solution of linear systems of equations using matrix triangularization procedures suitable for implementation on array architectures. Gaussian elimination with partial or pairwise pivoting and QR decomposition are made fault tolerant against two transient errors occurring during the triangularization procedure. The extended Euclidean algorithm is implemented to solve for the locations and values of the errors defined appropriately using the theory of error correcting codes. The Sherman-Morrison-Woodbury formula is then used to obtain the correct solution vector to the linear system of equations without requiring a valid decomposition.

UR - https://www.scopus.com/pages/publications/0026989617

M3 - Chapter

AN - SCOPUS:0026989617

SN - 0818629673

T3 - Proceedings of the International Conference on Application

SP - 469

EP - 480

BT - Proceedings of the International Conference on Application

PB - Publ by IEEE

T2 - Proceedings of the International Conference on Application Specific Array Processors

Y2 - 4 August 1992 through 7 August 1992

ER -

Fault tolerant matrix triangularization and solution of linear systems of equations

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this