COMPUTATIONAL PROBLEMS IN ABSTRACT ALGEBRA

By N. MAANA

CONTENTS A SHORT REVIEW OF LINEAR ALGEBRA NOTATION VECTOR SPACES AND SUBSPACES LINEAR INDEPENDENCE AND BASES SUBSPACES THE VECTOR SPACES RN AND CN LINEAR SYSTEMS BASIC PROPERTIES THE INVERSE MATRIX DETERMINANTS EIGENVALUES, EIGENVECTORS AND EIGENPAIRS EXERCISES CHAP 1 EXERCISES SECT 1 1 EXERCISES SECT 1 3 EXERCISES SECT 1 4 PART I LU AND QR FACTORIZATIONS DIAGONALLY DOMINANT TRIDIAGONAL MATRICES; THREE EXAMPLES CUBIC SPLINE INTERPOLATION POLYNOMIAL INTERPOLATION PIECEWISE LINEAR AND CUBIC SPLINE INTERPOLATION GIVE ME A MOMENT LU FACTORIZATION OF A TRIDIAGONAL SYSTEM A TWO POINT BOUNDARY VALUE PROBLEM DIAGONAL DOMINANCE AN EIGENVALUE PROBLEM THE BUCKLING OF A BEAM THE EIGENPAIRS OF THE 1D TEST MATRIX BLOCK MULTIPLICATION AND TRIANGULAR MATRICES BLOCK MULTIPLICATION TRIANGULAR MATRICES EXERCISES CHAP 2 EXERCISES SECT 2 1 EXERCISES SECT 2 2 EXERCISES SECT 2 3 EXERCISES SECT 2 4 EXERCISES SECT 2 5 REVIEW QUESTIONS GAUSSIAN ELIMINATION AND LU FACTORIZATIONS 3 BY 3 EXAMPLE GAUSS AND LU BANDED TRIANGULAR SYSTEMS ALGORITHMS FOR TRIANGULAR SYSTEMS COUNTING OPERATIONS THE PLU FACTORIZATION PIVOTING PERMUTATION MATRICES PIVOT STRATEGIES THE LU AND LDU FACTORIZATIONS EXISTENCE AND UNIQUENESS BLOCK LU FACTORIZATION EXERCISES CHAP 3 EXERCISES SECT 3 3 EXERCISES SECT 3 4 EXERCISES SECT 3 5 EXERCISES SECT 3 6 LDL* FACTORIZATION AND POSITIVE DE?NITE MATRICES THE LDL* FACTORIZATION POSITIVE DE?NITE AND SEMIDE?NITE MATRICES THE CHOLESKY FACTORIZATION POSITIVE DE?NITE AND POSITIVE SEMIDE?NITE CRITERIA SEMI-CHOLESKY FACTORIZATION OF A BANDED MATRIX THE NON-SYMMETRIC REAL CASE EXERCISES CHAP 4 EXERCISES SECT 4 2 ORTHONORMAL AND UNITARY TRANSFORMATIONS INNER PRODUCTS, ORTHOGONALITY AND UNITARY MATRICES REAL AND COMPLEX INNER PRODUCTS ORTHOGONALITY SUM OF SUBSPACES AND ORTHOGONAL PROJECTIONS UNITARY AND ORTHOGONAL MATRICES THE HOUSEHOLDER TRANSFORMATION HOUSEHOLDER TRIANGULATION THE ALGORITHM THE NUMBER OF ARITHMETIC OPERATIONS SOLVING LINEAR SYSTEMS USING UNITARY TRANSFORMATIONS THE QR DECOMPOSITION AND QR FACTORIZATION EXISTENCE QR AND GRAM-SCHMIDT GIVENS ROTATIONS EXERCISES CHAP 5 EXERCISES SECT 5 1 EXERCISES SECT 5 2 EXERCISES SECT 5 4 EXERCISES SECT 5 5 EXERCISES SECT 5 6 PART II EIGENPAIRS AND SINGULAR VALUES EIGENPAIRS AND SIMILARITY TRANSFORMATIONS DEFECTIVE AND NONDEFECTIVE MATRICES SIMILARITY TRANSFORMATIONS ALGEBRAIC AND GEOMETRIC MULTIPLICITY OF EIGENVALUES THE JORDAN FACTORIZATION THE SCHUR FACTORIZATION AND NORMAL MATRICES THE SCHUR FACTORIZATION NORMAL MATRICES THE RAYLEIGH QUOTIENT THE QUASI-TRIANGULAR FORM HERMITIAN MATRICES MINMAX THEOREMS THE HOFFMAN-WIELANDT THEOREM LEFT EIGENVECTORS BIORTHOGONALITY EXERCISES CHAP 6 EXERCISES SECT 6 1 EXERCISES SECT 6 2 EXERCISES SECT 6 3 EXERCISES SECT 6 4 THE SINGULAR VALUE DECOMPOSITION THE SVD ALWAYS EXISTS THE MATRICES A?A, AA? FURTHER PROPERTIES OF SVD THE SINGULAR VALUE FACTORIZATION SVD AND THE FOUR FUNDAMENTAL SUBSPACES A GEOMETRIC INTERPRETATION DETERMINING THE RANK OF A MATRIX NUMERICALLY THE FROBENIUS NORM LOW RANK APPROXIMATION EXERCISES CHAP 7 EXERCISES SECT 7 1 EXERCISES SECT 7 2 EXERCISES SECT 7 4 PART III MATRIX NORMS AND LEAST SQUARES MATRIX NORMS AND PERTURBATION THEORY FOR LINEAR SYSTEMS VECTOR NORMS MATRIX NORMS CONSISTENT AND SUBORDINATE MATRIX NORMS OPERATOR NORMS THE OPERATOR P-NORMS UNITARY INVARIANT MATRIX NORMS ABSOLUTE AND MONOTONE NORMS THE CONDITION NUMBER WITH RESPECT TO INVERSION PERTURBATION OF THE RIGHT HAND SIDE IN A LINEAR SYSTEMS PERTURBATION OF A SQUARE MATRIX PROOF THAT THE P-NORMS ARE NORMS P-NORMS AND INNER PRODUCT NORMS EXERCISES CHAP 8 EXERCISES SECT 8 1 EXERCISES SECT 8 2 EXERCISES SECT 8 3 EXERCISES SECT 8 4 LEAST SQUARES EXAMPLES CURVE FITTING GEOMETRIC LEAST SQUARES THEORY NUMERICAL SOLUTION NORMAL EQUATIONS QR FACTORIZATION SINGULAR VALUE DECOMPOSITION, GENERALIZED INVERSES AND LEAST SQUARES PERTURBATION THEORY FOR LEAST SQUARES PERTURBING THE RIGHT HAND SIDE PERTURBING THE MATRIX PERTURBATION THEORY FOR SINGULAR VALUES THE MINMAX THEOREM FOR SINGULAR VALUES AND THE HOFFMAN-WIELANDT THEOREM EXERCISES CHAP 9 EXERCISES SECT 9 1 EXERCISES SECT 9 2 EXERCISES SECT 9 3 EXERCISES SECT 9 4 EXERCISES SECT 9 5 PART IV KRONECKER PRODUCTS AND FOURIER TRANSFORMS THE KRONECKER PRODUCT THE 2D POISSON PROBLEM THE TEST MATRICES PROPERTIES OF THE 2D TEST MATRICES EXERCISES CHAP 10 EXERCISES SECTS 10 1, 10 2 EXERCISES SECT 10 3 FAST DIRECT SOLUTION OF A LARGE LINEAR SYSTEM ALGORITHMS FOR A BANDED POSITIVE DE?NITE SYSTEM CHOLESKY FACTORIZATION BLOCK LU FACTORIZATION OF A BLOCK TRIDIAGONAL MATRIX OTHER METHODS A FAST POISSON SOLVER BASED ON DIAGONALIZATION A FAST POISSON SOLVER BASED ON THE DISCRETE SINE AND FOURIER TRANSFORMS THE DISCRETE SINE TRANSFORM (DST) THE DISCRETE FOURIER TRANSFORM (DFT) THE FAST FOURIER TRANSFORM (FFT) A POISSON SOLVER BASED ON THE FFT EXERCISES CHAP 11 EXERCISES SECT 11 3 PART V ITERATIVE METHODS FOR LARGE LINEAR SYSTEMS THE CLASSICAL ITERATIVE METHODS CLASSICAL ITERATIVE METHODS; COMPONENT FORM THE DISCRETE POISSON SYSTEM CLASSICAL ITERATIVE METHODS; MATRIX FORM FIXED-POINT FORM THE SPLITTING MATRICES FOR THE CLASSICAL METHODS CONVERGENCE RICHARDSON’S METHOD CONVERGENCE OF SOR CONVERGENCE OF THE CLASSICAL METHODS FOR THE DISCRETE POISSON MATRIX NUMBER OF ITERATIONS STOPPING THE ITERATION POWERS OF A MATRIX THE SPECTRAL RADIUS NEUMANN SERIES THE OPTIMAL SOR PARAMETER ? EXERCISES CHAP 12 EXERCISES SECT 12 3 EXERCISES SECT 12 4 THE CONJUGATE GRADIENT METHOD QUADRATIC MINIMIZATION AND STEEPEST DESCENT DERIVATION OF THE METHOD THE CONJUGATE GRADIENT ALGORITHM NUMERICAL EXAMPLE IMPLEMENTATION ISSUES THE MAIN THEOREM THE NUMBER OF ITERATIONS FOR THE MODEL PROBLEMS KRYLOV SPACES AND THE BEST APPROXIMATION PROPERTY PROOF OF THE CONVERGENCE ESTIMATES CHEBYSHEV POLYNOMIALS CONVERGENCE PROOF FOR STEEPEST DESCENT MONOTONICITY OF THE ERROR PRECONDITIONING PRECONDITIONING EXAMPLE A VARIABLE COEF?CIENT PROBLEM APPLYING PRECONDITIONING EXERCISES CHAP 13 EXERCISES SECT 13 1 EXERCISES SECT 13 2 EXERCISES SECT 13 3 EXERCISES SECT 13 4 EXERCISES SECT 13 5 PART VI EIGENVALUES AND EIGENVECTORS NUMERICAL EIGENVALUE PROBLEMS EIGENPAIRS GERSHGORIN’S THEOREM PERTURBATION OF EIGENVALUES NONDEFECTIVE MATRICES UNITARY SIMILARITY TRANSFORMATION OF A MATRIX INTO UPPER HESSENBERG FORM ASSEMBLING HOUSEHOLDER TRANSFORMATIONS COMPUTING A SELECTED EIGENVALUE OF A SYMMETRIC MATRIX THE INERTIA THEOREM APPROXIMATING ?M EXERCISES CHAP 14 EXERCISES SECT 14 1 EXERCISES SECT 14 2 EXERCISES SECT 14 3 EXERCISES SECT 14 4 EXERCISES SECT 14 5 THE QR ALGORITHM THE POWER METHOD AND ITS VARIANTS THE POWER METHOD THE INVERSE POWER METHOD RAYLEIGH QUOTIENT ITERATION THE BASIC QR ALGORITHM RELATION TO THE POWER METHOD INVARIANCE OF THE HESSENBERG FORM DE?ATION THE SHIFTED QR ALGORITHMS EXERCISES CHAP 15 EXERCISES SECT 15 1