Linear Algebra - Revision history

Admin: /* The Big-O cost of Matrix Inversion */

2017-09-24T09:09:15Z

The Big-O cost of Matrix Inversion

← Older revision		Revision as of 09:09, 24 September 2017
Line 471:		Line 471:
	But if we are clever, we can do it in 7 multiplications (with more addition - b/c there is no free lunch)		But if we are clever, we can do it in 7 multiplications (with more addition - b/c there is no free lunch)

	This reduces the cost from <math>O(N^3)</math> to <math>O(N^{\log_2{7})</math>		This reduces the cost from <math>O(N^3)</math> to <math>O(N^{\log_2{7}})</math>

	Fast matrix multiplication routines are more common in libraries like BLAS		Fast matrix multiplication routines are more common in libraries like BLAS

2017-09-24T09:09:01Z

QR Decomposition

← Older revision		Revision as of 09:09, 24 September 2017
Line 456:		Line 456:
	Why use QR decomposition? If your numerical algorithm requires solving succession of linear systems, each A being slightly different, LU decomposition will require <math>O(N^3)</math> operations each time. QR decopmosition can be updated with only <math>O(N^2)</math> operations.		Why use QR decomposition? If your numerical algorithm requires solving succession of linear systems, each A being slightly different, LU decomposition will require <math>O(N^3)</math> operations each time. QR decopmosition can be updated with only <math>O(N^2)</math> operations.

	QR decomposition is simple to update if A changes according to <math>\mathbf{A} \rightarrow \mathbf{A} + \mathbf{s \~~ocross~~ t}</math> - this only changes the matrix R to be slightly different		QR decomposition is simple to update if A changes according to <math>\mathbf{A} \rightarrow \mathbf{A} + \mathbf{s \otimes t}</math> - this only changes the matrix R to be slightly different

	Two phases:		Two phases:

2017-09-24T09:08:47Z

QR Decomposition

@@ Line 454: / Line 454: @@
 Householder matrix is of the form <math>\mathbf{1} - \mathbf{u \otimes u}/c</math>, where <math>\mathbf{c} = \dfrac{1}{2} \mathbf{u \cdot u}</math>
 [[Category:Numerics]]
 [[Category:Numerical Recipes]]
 [[Category:Linear Algebra]]

2017-09-24T08:51:43Z

Cholesky Decomposition

← Older revision		Revision as of 08:51, 24 September 2017
Line 433:		Line 433:
	\mathbf{v \cdot A \cdot v} > 0 \quad \forall \, \mathbf{v}		\mathbf{v \cdot A \cdot v} > 0 \quad \forall \, \mathbf{v}
	</math>		</math>

			Symmetric, positive-definite matrices occur in some applications

			Colesky decomposition is an efficient triangular decomposition

			Rather than decomposing <math>\mathbf{A} = \mathbf{L \cdot U}</math>, Cholesky decomposition decomposes A into <math>\mathbf{A} = \mathbf{L \cdot L^{T}}</math>

			(also referred to as the square root of A)

			Cholesky decomposition is numerically stable without pivoting

			Failure of Cholesky Decomposition indicates A is not positive definite (can actually use Cholesky decomposition as a test of ''whether'' a matrix is positive definite)

			==QR Decomposition==

			QR decomposition requires twice the number of operations of LU decomposition. Not the general go-to method, but useful for some purposes.

			QR decomposition is accomplished by performing a series of Householder transformations

			Householder matrix is of the form <math>\mathbf{1} - \mathbf{u \otimes u}/c</math>, where <math>\mathbf{c} = \dfrac{1}{2} \mathbf{u \cdot u}</math>

2017-09-24T08:40:47Z

Cholesky Decomposition

← Older revision		Revision as of 08:40, 24 September 2017
Line 431:		Line 431:

	<math>		<math>
	\mathbf{v \cdot A \cdot v} > 0 \quad \forall \mathbf{ v}		\mathbf{v \cdot A \cdot v} > 0 \quad \forall \, \mathbf{v}
	</math>		</math>

2017-09-24T08:40:35Z

Cholesky Decomposition

← Older revision		Revision as of 08:40, 24 September 2017
Line 431:		Line 431:

	<math>		<math>
	\mathbf{v \cdot A \cdot v} > 0 \quad \forall \mathbf{v}		\mathbf{v \cdot A \cdot v} > 0 \quad \forall \mathbf{ v}
	</math>		</math>

2017-09-24T08:40:15Z

Toeplitz Matrices

← Older revision		Revision as of 08:40, 24 September 2017
Line 424:		Line 424:
	Levinson's method takes <math>O(N^2)</math> operations to solve. Newer, faster methods have come out that require <math>N (\log N)^2</math> operations instead of <math>N^2</math> for Levinson's method, but these algorithms are more complicated. (See Bunch and de Hoog.)		Levinson's method takes <math>O(N^2)</math> operations to solve. Newer, faster methods have come out that require <math>N (\log N)^2</math> operations instead of <math>N^2</math> for Levinson's method, but these algorithms are more complicated. (See Bunch and de Hoog.)

			==Cholesky Decomposition==

			Solving a linear system with a symmetric and positive definite matrix A can be solved using a more efficient triangular decomposition method.

			Note: positive definite means

			<math>
			\mathbf{v \cdot A \cdot v} > 0 \quad \forall \mathbf{v}
			</math>

2017-09-22T04:09:58Z

Linear Algebra Software

← Older revision		Revision as of 04:09, 22 September 2017
Line 54:		Line 54:
	* Linear least-squares problem can be used to solve overdetermined linear system		* Linear least-squares problem can be used to solve overdetermined linear system

	==Linear Algebra Software==		===Linear Algebra Software===

	Software:		Software:

2017-09-22T04:09:46Z

Tasks of Computational Linear Algebra

← Older revision		Revision as of 04:09, 22 September 2017
Line 35:		Line 35:
	* Larger sets of thousands or millions of equations can be solved with coefficients are sparse (mostly zero) by using specialty sparse methods		* Larger sets of thousands or millions of equations can be solved with coefficients are sparse (mostly zero) by using specialty sparse methods

	==Tasks of Computational Linear Algebra==		===Tasks of Computational Linear Algebra===

	Beyond simply solving Ax=b for the unknowns x, we may want to do other things:		Beyond simply solving Ax=b for the unknowns x, we may want to do other things:

2017-09-22T04:09:37Z

Nonsingular vs Singular

← Older revision		Revision as of 04:09, 22 September 2017
Line 15:		Line 15:
	where lowercase letters denote vectors, and the dot represents multiplication of two matrices or a matrix and a vector, or dot product of two vectors.		where lowercase letters denote vectors, and the dot represents multiplication of two matrices or a matrix and a vector, or dot product of two vectors.

	==Nonsingular vs Singular==		===Nonsingular vs Singular===

	We are not guaranteed to find a solution to a given linear system Ax=b		We are not guaranteed to find a solution to a given linear system Ax=b