Home

Wang-K-dissertation - Department of Computer Science

1. 2 4 11 4 1 4 2 Error Message Error Message Pass 6 16 7 14 3 32 3 15 9 Il 3 1 3 5 5 Null Error Message Error Message Pass 9 8 3 8 2 4 Gaussian Jordan Reduction Matrix A Expected Result Actual Result Status 2011 4 100 0 1 0 O 0 Pass 707 14 00 1 0 00 1 0 3 0 3 15 000 1 00 0 I 90 3 4 0000 0000 null Error Message Error Message Pass Determinant Matrix A Expected Result Actual Result Status 1 1 2 16 16 Pass 3 1 4 0 2 5 null Error Message Error Message Pass Rank Matrix A Expected Result Actual Result Status 73 Linear Algebra System 1 12 3 3 Pass 3 1 4 0 2 5 null Error Message Error Message Pass Matrix Inverse Matrix A Expected Result Actual Result Status 2 3 D5 15 35 j5 ES 4 5 2 1 2 1 2 3 4 Null Null Pass 1 2 Null Null Pass Null Null Null Pass Matrix Inverse Blockwise Matrix A Expected Result Actual Result Status 2 3 Da 72721906E9 1 462152112E10 Fa 4 5 2 1 1 406588E7 2 798348E7 2 3 4 Null Null Pass 1 2 Null Null Pass Null Null Null Pass Transpose Matrix A Expected Result Actual Result Status PES SS 1 ej 130 Beil 3 1 4 3 1 4 1 1 2 0 2 5 0 2 5 245 Null Null Null Pass 74 Linear Algebra System 7 3 Input Testing and User Interface Test Because the users have to use the interface to input numbers
2. colCountertt if colCounter tmp getCols amp amp tmp get row colCounter isZero System out println this is not a invertible matrix 85 Linear Algebra System check return false if break return check tmp get row false colCounter isZero public static Matrix simple Matrix m if m getRows return null Matrix tmp m copy FieldElement zero tmp get 1 FieldElement one zero on FieldElement entries2 getCols m getCols 1 zero O new FieldElement tmp getRows tmp for int i 0 i lt tmp getRows i for int j 0 j lt tmp getCols j if i 3 entries2 i jl else entries2 i jl Matrix tmp2 0 int minOfRowsCols int colCounter int row 0 while rowrr colCounterrr Math min tmp getRows one zero new Matrix entries2 tmp getCols row lt minOfRowsCols amp amp colCounter lt tmp getCols 86 Linear Algebra System FieldElement diagonalEntry tmp get row colCounter if diagonalEntry isZero search for non zero entry boolean found false for int candidate row 1 candidate lt tmp getRows candidate t if tmp get candidate colCounter isZero tmp swapRows row candidate tmp2 swapRows row candidate found true break if found if colCount
3. param ml param m2 return ml multiplied by m2 throws InvalidOperationException public static Matrix coppersmithWinograd Matrix ml Matrix m2 checkDimensions ml m2 if checkSize ml1 m2 int endIndex ml getRows int splitIndex endIndex 2 Matrix all ml getMatrix 1 splitIndex 1 splitIndex Matrix al2 ml getMatrix 1 splitIndex splitIndex 1 endIndex Matrix a2l ml getMatrix splitIndex 1 endIndex 1 splitIndex 94 Linear Algebra System Matrix a22 ml getMatrix splitlIndex 1 endIndex splitIndex 1 endIndex Matrix bll Matrix b12 m2 getMatrix 1 splitIndex 1 splitIndex m2 getMatrix 1 splitIndex splitIndex 1 endIndex Matrix b21 m2 getMatrix splitIndex 1 endIndex 1 splitIndex Matrix b22 m2 getMatrix splitIndex 1 endIndex splitIndex 1 endIndex Matrix sl a21 add a22 Matrix s2 sl subtract all Matrix s3 all subtract a21 Matrix s4 al2 subtract s2 Matrix tl bl2 subtract 011 Matrix t2 b22 subtract tl Matrix t3 b22 subtract 012 Matrix t4 b21 subtract t2 Matrix pl coppersmithWinograd all b11 Matrix p2 coppersmithWinograd al2 b21 Matrix p3 coppersmithWinograd sl tl Matrix p4 coppersmithWinograd s2 t2 Matrix 5 coppersmithWinograd s3 t3 Matrix p6 coppersmithWinograd s4 b22
4. add leftBra numeratorl Slash tries 3 denominatorEntries add rightBra tp is the text get from the selection of the number type comobo box and jc is the panel to show the entries When creating complexNum entries in order to make the users clear about which entry refers to the real part of a complex number and which entry refers to the imaginary part of a rational number They system will put a between the real part and imaginary part and a i after the imaginary part and a bracket around each single number Code if tp equals Complex Number JTextField realEntries new JTextField 3 JTextFiel imaginaryEntries new JTextField 3 add new JLabel symbol new JLabel i C CQ C leftBra new JLabel jc add jc add jc add jc add jc add jc add Read entries rightBra new JLabel leftBra realEntries add imaginaryl Entries symbol rightBra When the users click confirm button the system will read the input from TextField to create a vector or matrix Reading entries was a pain during coding the interface There were two problems 1 Because there are not only TextField in the entry panel so when the system traces the components in the panel and reads the text in it it is easy
5. 4 5 tr A tr B 6 tr AB 7 ctr A 8 tr A Inverse Definition if there is a matrix B can make A B B A I we say matrix A is invertible and is A s inverse Moreover there is only one inverse for an invertible matrix 2 5 3 5 A B MES 23 5xCD 2 5 5 21 1 O 1x3 1 x3 IX 3 2X9 0 1 10 Ais an n n matrix process of finding a inverse of a matrix is Example And 1 Adjoin A with identity matrix Ip The new matrix is A I 2 Compute the reduced echelon form of A I 3 If the reduced echelon form is in the form of 1 B then B is the inverse If not A does not have inverse Example A P 3 2 SoA 55 1 2 1 2 1 0 10 3 2 nd k 1 f jx Theorem In the system of equation AX Y if matrix A is invertible then the solution is unique If A is an invertible matrix then A is and invertible matrix 3 Linear Algebra System 2 3 4 Determinants of Square Matrices 2 3 4 1 What are determinants a Definition for the matrix A its determinant 122 Definition for the square matrix A its Minor of element ay denoted as Mi is the determinant of the matrix A after deleting row i and column j The Cofactor of aj denoted as is defined as C1 My Definition The determinant of a square matrix is the sum of the product of on
6. Matrix 7 coppersmithWinograd a22 t4 Matrix ul pl add p2 Matrix u2 pl add p4 Matrix u3 u2 add p5 Matrix u4 u3 add p7 Matrix u5 u3 add p3 Matrix u6 u2 add p3 Matrix u7 u6 add p6 FieldElement cllEntries ul getEntries FieldElement cl2Entries u7 getEntries FieldElement c21Entries u4 getEntries FieldElement c22Entries u5 getEntries 95 Linear Algebra System FieldElement cEntries new FieldElement ml getRows m2 getCols for int i 0 i lt ul getRows i for int j 0 j lt ul getCols j cEntries i j cllEntries i j for int i 0 i lt u7 getRows i int offset splitIndex for int j 0 j lt u7 getCols j cEntries i j splitIndex cl2Entries i j for int i 0 i lt u4 getRows i int offset splitIndex for int j 0 j lt u4 getCols j cEntries i splitIndex j c21Entries i jl for int i 0 i lt u5 getRows i int offset splitIndex for int j 0 j lt u5 getCols j cEntries i splitIndex j splitIndex c22bEntries i jl return new Matrix cEntries return simple ml m2 96 Linear Algebra System 11 Appendix B User Manual This software is quite easy to use There are five tabbed panel in the application window which are Vector A Vec
7. Summary 1 User input two vector 2 Then the system outputs the result of subtracting a vector to another vector Rationale This is the basic vector arithmetic Index 5 Name Vector Multiplication Scalar Summary 1 User input the vector and scalar 2 Then the system outputs the result of multiplying a vector by a scalar Rationale This is the basic vector arithmetic Index 6 Name Vector Multiplication Vector Summary 1 User input two vectors 2 Then the system outputs the result of multiplying two vectors Rationale This is the basic vector arithmetic Index 7 Name Vector Multiplication Matrix Summary 3 User input a vector and matrix 4 Then the system outputs the result of multiplying the vector and matrix Rationale This is the basic vector arithmetic Index 8 Name Dot Product Summary 1 User input two vectors 2 Then the system outputs the dot product of two vectors 39 Linear Algebra System Rationale This is the basic vector arithmetic Index 9 Name Cross Product Summary 1 User input two vectors 2 Then the system outputs the cross product of two vectors Rationale This is the basic vector arithmetic Index 10 Name Vectors Distance Summary 1 User input two vectors 2 Then the system outputs the distance between two vectors Rationale This is the basic vector arithmetic Index 11 Name Vector Cosine Summary 1 User input two vectors 2 Then the system outputs
8. not 1000 1000 1000 01 O 0 0 1 0 0 0 1 0 0 0 0 1 3 00 1 0 0 1 O 0 00 0 I 100 1 Gauss Jordan Elimination We are using Gauss Jordan Elimination to complete transforming a matrix into the reduced echelon form which is a version of Gaussian elimination 1 Write down the augmented matrix of the system of linear equations Linear Algebra System 2 Change the matrix to reduced echelon form by using elementary row operations Starts from find the first leading 1 column by column from left to right then make the element above or before leading 1 zero 3 Apply the reduced Echelon form to the system of equation to get the result Example 4x 3x3 2 8 11x3 7 6x 7x3 3 so the augmented matrix is 14 3 1 2 8 11 7 1 6 7 3 Using the Gauss Jordan Elimination 4 3 1 143 1 1 3 1 2 8 Il 7 0055 1 7 3 1 6 7 3 Ram 1 6 7 3 0 0 5 5 i R3 R1 2 C 7 3 1 4 3 1 0 5 3 0 4 2 0121 0 100 5 5 0 0 1 1 R 4 00 1 1 R3 1 5 0 0 0103 5R3 0011 R2 2RI Xi 2 3 X3 So the solution for this system of equation is 2 2 3 1 Solution We can only use reduced echelon form to solve the system of equation of which the number of variables is same as the number given equations However even under this condition the solution has three different situations unique solution many solutions and no solution The discussion about how to judge the
9. they also use the straOriginal method Then it calculates from to Matrix pl strassenOriginal all add a22 bll add b22 Matrix p2 strassenOriginal a2l add a22 b11 Matrix p3 strassenOriginal all bl2 subtract b22 Matrix p4 strassenOriginal a22 b21 subtract 011 Matrix p5 strassenOriginal all add al2 b22 Matrix strassenOriginal a2l subtract all bll add b12 Matrix p7 strassenOriginal al2 subtract a22 b21 add b22 Matrix cll pl add p4 subtract p5 add p7 Matrix 12 p3 add p5 Matrix c21 p2 add p4 Matrix c22 pl add p3 subtract p2 add The final step is reconstructing the matrix from to C to get the final result Detail can be seen from Appendix A MatrixMultiplication class 6 3 2 CopperWinograd It uses Coppersmith Winograd algorithm to calculate two matrices multiplication It requires same pre conditions and goes through same steps of process The differences are temporary objects it creates and the computations between these objects Regarding with the code the differences are different name and number of objects and objects operations The structure and the basic idea is as same as that in straOriginal Detail can be seen from Appendix A MatrixMultiplication class 6 3 3 blockWiseInverse It uses Blockwise algorithm to calculate the inverse of the matrix The pre condition of this algorithm is that A and delta is in
10. Matrix tmpl mTranspose multiply m Matrix tmpl m gausselim int endIndex tmpl getRows 88 int splitIndex Linear Algebra System endIndex 2 Matrix all tmpl getMatrix 1 splitIndex 1 splitIndex Matrix al2 tmpl getMatrix 1 splitIndex splitIndex 1 endIndex Matrix a21 tmpl getMatrix splitIndex 1 endIndex 1 splitIndex Matrix 22 tmpl getMatrix splitIndex 1 endIndex splitIndex 1 endIndex tmp2 is the temporary matrix used to calculate the delta ali 12 21 22 System out printin toString a System out print toString System out println toString System out printin toString Matrix allInverse blockWiselnverse all Matrix delta delta delta a21 multiply allInverse delta multiply a12 a22 subtract delta Matrix deltaInverse blockWiselnverse delta System out println delta deltatdeltaInversetalliInverset n the code below is to calculate the inverse of tmpl Matrix cll allInverse multiply a12 System out println cll toString cllzcll multiply deltaInverse System out println cll toString 11 cll multiply a21 System out printin cll toString c11 cll multiply allInverse System out println cll toString cllzallInverse add cll System out println cll toString Matrix 12 allInverse multipl
11. Pass 1 2 1 4 2 3 124 4 8 1019 5 10 4 8 10 5 10 Pass 4 7 2 2 61 3431 9471 Error Message Error Message Pass 2 61 3 31 9 71 4 7 2 Error Message Error Message Pass 1 2 1 4 2 3 2 61 3 31 9 7 Error Message Error Message Pass 1 1 2 4 4 1 1 2 1 4 2 3 Error Message Error Message Pass Vector Norm Vector A Expected Result Actual Result Status 3 6 1 6 78232998 6 78232998 Pass 3 5 5 8 1 3 0 92829742 0 92829742 Pass 70 Linear Algebra System 1 1 2 i 4 1 Error Message Error Message Pass 7 2 2 Matrix Functions In the last part of testing when testing each function the system is also testing the number s function Actually testing the number s function is the real target of testing the functions working between different types of numbers Since this function testing has passed there is no need to test calculations between different numbers afterward Moreover as it is mentioned in the Testing Principle functions with high hierarchy have the priority to be tested So the matrix addition matrix multiplication matrix and Gaussian Elimination will not be tested in here Subtraction Scalar Matrix A Scalar Expected Result Actual Result Status 355 3 0 2 2 022 Fass 9 8 3 6 5 0 6 5 0 8 2 4 5 1 1 5 11 3 5 5 null Error Message Error Message Pass 9 8 3 8 2 4 Subtraction Matrix Matrix A Matrix B Expected Resu
12. create a system which applies the algorithms of Linear Algebra to solve matrices and vectors based problem the scope of the project is only focused on the matrices and vectors based computation So in the later work I need find out what kind of operations and algorithms apply to matrices and vectors there are and how they work What s more since there have been already many mathematical systems invented my project could be considered as a scale reduced version of other systems Then it is necessary to research and analyse the current mathematical systems The reason it is necessary is because I need to prove the knowledge I gain from Linear Algebra is applicable and the previous work will give me some ideas and directions in the later work of designing the system There are two sections in this review which are Linear Algebra explaining the academic understanding on Linear Algebra and current system discussing two current systems Maple and Matlab 2 2 Numbers A number is a mathematical concept and an abstract entity used to representing a quantity and express how many things are being referred to or how much there is of some thing or property It can be a count tool for individual objects and also to measure quantities such as length area weight and time 1 2 2 1 Rational Number Rational number is the subset of real number which also includes irrational number and can be described informally as numbers that can be given by a
13. simple methods to use the standard ways to do calculation The checkDimension in MatrixMultiplication is to check if two matrix have right dimension to multiply with each other The checkSize is to check if the dimension of two matrix meet the pre condition of using Strassen Algorithm or Coppersmith Winograd The checkSingular is to check if the matrix is invertible If it is invertible the system will do the inverse or the system terminates the process 5 3 2 Class Association Model Consist of Compute on Call it for calculations Implement on The relation between classes is that the Field vector or matrix is firstly constructed with FieldElements as entries When the Field wants to implement some function or use the advanced algorithms it actually do the calculation on FieldElements The FieldElement will call Operator to finish some calculations 5 4 AI Design The AI requirement in the 3 3 mentioned about two methods of implement AI The first method can be achieved by checking the matrix form in the early stage of calculating the determinant of a matrix The second methods after the careful consideration will be implemented in this way Although after analysing the matrix feature and find the row or column has the most zeros it still uses the standard algorithm to calculate the determinant of matrix which has the complexity of n 12 It means in a n n matrix even there a
14. 0 then it swaps with another row with non zero entry in the first column if the whole column entries are all Zeros it goes to the entry next to diagonal and do checking again if diagonalEntry isZero search for non zero entry boolean found false for int candidate row 1 candidate lt tmp getRows candidatet if tmp get candidate colCounter isZero tmp swapRows row candidate found true break if found if colCounter tmp getCols return tmp row continue else diagonalEntry tmp get row colCounter The if is to check the diagonal entry and the for loop is to find a row with non zero entry can be swapped If the row is found the for loop breaks The second if is about checking if the non zero entry can be found or not So if it is not found and the process is in the last column it returns the tmp which is the matrix to store row echelon form of the original matrix Or row and continue to go to the entry next to the diagonal However if it is found it set the current diagonal entry to diagonalEntry to do the later process 2 After finding the non zero diagonal it implements the row operations to make the entries denoted as non diagonal entry in the following with same column index as the diagonal and row index below the diagonal zero To do this it needs to factorise the row denoted as non
15. 0040202400000000000000000 nennen 52 Implementation AE 52 6 1 Introduction nen ae AT 52 6 2 Number Structure and General Functions essen 53 6 2 1 53 6 2 2 NGCLOL ET 54 6 2 3 oe NM Lt 55 6 3 Advanced Algorithms and 61 6 3 1 straOrigin l edidi 61 6 3 2 CopperWinograd sess enne enne nen entren nennen 62 6 3 3 block WiseInverse 62 6 3 4 MO MEME IR 63 User niei encon nona IE ERES FERE evade 63 6 5 Error and Exception 65 ETE T 66 7 Testing Objectives and Principles 2 2 66 7 2 Function Testing een ed eet 67 7 2 1 Vector 67 7 2 2 Matrix 71 7 3 Input Testing and User Interface 75 Conclusi n MEE 77 8 1 Evaluation and Critiques ener nennen nennen T 8 1 1 Achievement MM 77 8 1 2 rub P O A 78 8 2 Further Developments tente eie eret rera eei 78 8
16. 2 1 Nn CER 78 8 2 2 Linear Algebra Funct Ons i aee GR E TD FY 78 8 2 3 User E 79 Linear Algebra System 8 2 4 Advanced 79 8 2 5 Artificial Intelligence 79 9 Bibliography cute ee 80 10 Appendi amp A M 81 11 Appendix User Manual essere nennen nennen 97 Linear Algebra System 1 Introduction Linear Algebra is a central course in undergraduate mathematics which is placed as the beginning of abstract mathematics It also plays an important role in other areas such as natural sciences and social sciences When we use the theories of Linear Algebra to solve problem in most time we deal with matrix calculations It s stmple when we do 2 by 2 or 3 by 3 matrix operation using pen and paper However it takes hours or days to do computations on tens or hundreds of dimension matrices So a Linear Algebra based mathematical system is quit necessary In fact currently there has been some mathematic software created for solving matrices calculation such as Maple Matlab Mathematica and so on However these softwares also cover other aspects of mathematics which makes the software complicated to use and learn It s quite useful for a mathematician doing cross fields computations but it is very wasteful for the users who only want to do s
17. 3 2 31 2 1 4 1 1 2 1 4 2 3 1 2 1 21 1 2 1 21 Pass 1 2 1 41 1 2 1 41 8 3 2 31 8 3 2 31 Vector Multiplication Matrix Vector A Matrix A Expected Result Actual Result Status 1 2 6 2 4 1 16 16 Pass 3 1 7 2 4 Error Message Error Message Pass 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 2 43 42 43 42 Pass 124 1 2 1 4 2 3 11 3 11 3 Pass 1 2 1 4 2 3 124 11 3 11 3 Pass 4 7 2 2 1 4 1 26 13i 8 241 21 211 Pass 18 141 211 4 1 4 7 2 26131 8 241 21 211 Pass 18 141 1 2 1 4 2 3 1 i 2 i 4 1 11 3 17 121 11 3 17 121 Pass 241 4 1 1 2 1 4 2 3 11 3 17 121 11 3 17 121 Pass Vector Division Scalar Vector Scalar Expected Result Actual Result Status 3 2 11 0 6 0 4 2 2 0 6 0 4 2 2 Pass Null 3 Error Message Error Message Pass 5 2 8 3 20 7 2 5 4 4 3 10 7 5 1 16 3 40 7 Pass 2 1 4 1 2 1 2 1 21 1 1 21 1 2 1 21 1 1 21 Pass 2 1 21 2 1 21 Cross Product Vector A Vector B Expected Result Actual Result Status 3 6 1 2 5 1 1 13 1 13 Pass 317 2 4 Error Message Error Message Pass 4 7 2 Null Error Message Error Message Pass 69 Linear Algebra System 1 3 3 2 4 7 1 4 1 3 3 2 173 84 5 14 173 8
18. 3 Rank Eigenvalues and Eigenvectors Rank Definition the dimension of the row space and the column space of a matrix A is called the rank of A The rank of A is denoted rank A 22 Linear Algebra System To calculate the rank of nonzero row vectors of a matrix we need change the matrix to reduced echelon form first Then the number of nonzero row vectors is the rank Eigenvalues and Eigenvectors Definition A is an n n Matrix If there exist a scalar A and nonzero vector x such that Ax Ax Then we call x eigenvector and eigenvalue Theorem Let A be and matrix Then A 15 an eigenvalue of A is and only if p 4 4 A 1 0 Example 1 1 4 3 2 1 2 1 1 l 4 4 Then A AI 3 2 4 4 1 4 2 4 3 0 1 1 A Thus the eigenvalue of Aare A 21 4 2 4 3 0 1 4 x 0 For 4 1 we have A I V 3 1 0 2 do selbe 0 Then X 4 V 4 1 1 For 4 3 wehave V 2 1 For A 2 have V 2 4 Advanced Algorithms In this part some algorithms will be introduced which do the same computations as the previous basic algorithms but with lower complexities 23 Linear Algebra System 2 4 1 Complexity The concept of complexity should be explained in order to understand more clearly about the necessity of introducing the advanced algorithms The complexity in here is about the computational complexity which describes the scala
19. Coppersmith Winograd algorithm eese 25 2 4 4 Blockwise inversion Frobenius 26 2 4 5 Artificial Intelligence anaiai 27 25 RWYF SAN FFF TH RF FENNI FEN HAFAU 27 2 5 1 EE 27 2 5 2 ME 28 Requirements Analysis and Specification esses nennen 29 3 1 Die eil 29 32 USE CASES CPP 29 3 2 1 SCOP C I 29 3 2 2 Vector Use 30 3 2 3 Matrix Use Cas earannan 32 3 3 34 3 3 1 Linear Algebra 34 3 3 2 Advanced Algorithms eese nennen nennen 34 3 3 3 Artificial Intelligence nennen enne NND Don 35 3 3 4 User Interface u a t 35 3 4 Number Structure Input and 36 3 4 1 Number Structure 36 3 4 2 Data Input and enne 36 3 5 Error and Exception 36 3 6 Testing Requirement uH REG NI ROUEN 36 3 7 General nnn nennt nennen nnn entres 37 3 7 1 Operating System and Hardware Requirement 37 3 7 2 Programming 37 3 7 3 T
20. ErrorMess createErr e getMessage to create a err message 7 Testing 7 1 Testing Objectives and Principles The software testing is to find out how correctly completely securely and efficiently is developed It also test if software achieves the requirements and how well it behaviour Objectives This first feature of this project is that it is a user interactive software It allows the users input and after operations delivers output to the users So the first part of testing should be input testing It involves checking if the provide the users a interface to communicate if the system can read the user s input correctly The second feature is that this is a mathematical software project which means the correctness is the most important So the testing will focus on the correctness testing which is test if the system delivers a right output This part of is about the functional testing It also checks the completeness of the functional requirement in chapter 4 The user interface is the only way to communicate with the users for the system So it is also necessary to have an interface testing 66 Linear Algebra System Principles This system uses three number types So when testing functions it should be concerned if these functions works on all three types of number However if in some circumstance it has successfully pass the test on one type of number then it may not have to test for other types of number For exam
21. FieldElement s methods Fox exmaple Norm public FieldElement norm FieldElement temp new DoubleNum 0 for int i 0 i lt entries length itt temp temp add entries i power 2 0 return temp power 0 5 This method is to calculate the norm of a vector The for loop goes through every entry of the vector The statement in the for loop is to apply the norm algorithm to calculate the norm temp temp add entries i power 2 0 which adds all entries after square power Operators In vectors operations the add subtract multiply and divide functions use the operator concept This is designed for increasing the maintainability of the system public Vector add Vector anotherVector throws InvalidOperationException 54 Linear Algebra System return operate this anotherVector new AddOperator add Step 1 when using add method to add one vector with another the system calls operate this anotherVector new AddOperator add method Step 2 Checks the length of two vectors first Only if the check_length is successful the system will continue to next process Step 3 The system goes through each FieldElement objects in the Vector array and invokes the apply method in AddOperator class Step 4 then apply method calls the add method in FieldElement class to adds two FieldElement object and return the result of the addition Step 5 Storing each FieldEleme
22. Linear Algebra System 3 3 Project Functions 3 3 1 Linear Algebra Arithmetic Since this project is about deal with linear algebra field solving the fundamental linear algebra computations should be the primary requirements which are In Vector Area Vectors Addition Subtraction Vectors Multiplication Vectors Dot Product Vectors Cross Product Vectors Distance Vectors Cosine Vector Norm Matrix Area Matrices Addition Subtraction Matrices Multiplication Matrix Determinant Matrix Row Echelon Form Matrix Reduced Row Echelon Form Matrix Determinant Matrix Rank Matrix Transpose Matrix Inverse 3 3 2 Advanced Algorithms As what is discussed in the Literature Review there are three different algorithms calculating the matrices multiplication and inverse Recalling the third objective of this project developing these three algorithms will be the core in the advanced stage Although these algorithms have the lower time complexity than the standard ones they still have some constraints It is because the Asymptotic Notation is based the big scale of input which means that it only works properly in large dimension of matrices For a small dimension matrix like a 3 3 matrix the standard algorithms are more applicable So the system should have options for the users to choose between standard algorithms and these algorithms 34 Linear Algebra System 3 3 3 Artificial Intelligence The reason consid
23. System FieldElement diagonalEntry tmp get row colCounter if diagonalEntry isZero search for non zero entry boolean found false for int candidate row 1 candidate lt tmp getRows candidate t if tmp get candidate colCounter isZero tmp swapRows row candidate rowswap negate found true break if found if colCounter tmp getCols return tmp row continue else diagonalEntry tmp get row colCounter for int j row j lt tmp getRows j FieldElement factor tmp get j colCounter divide diagonalEntry if row j factor isZero continue for int k colCounter k lt tmp getCols k FieldElement oldEntry tmp get j k tmp set j oldEntry subtract factor multiply tmp get row 84 Linear Algebra System cowMul rowMul multiply 11 return tmp MatrixInverse Class package Backend public class MatrixInverse private static int FROBENIUS_POINT 48 Check if the matrix is a square matrix xu public static boolean checkSingular Matrix m boolean check true if m getRows m getCols check false else Matrix tmp m copy int minOfRowsCols Math min tmp getRows tmp getCols int colCounter 0 int row 0 while row lt minOfRowsCols rowt t while colCounter lt tmp getCols
24. Users Users choose the cosine function from the system Users input two vectors Users press compute button Users get the result 31 Task Primary Actor Preconditions Process Result Use case 8 Vector Norm Task Primary Actor Preconditions Process Result Linear Algebra System Calculating the distance between two vectors Users Users choose the distance function from the system Users input two vectors Users press compute button Users get the result Calculating the norm of a vector Users Users choose the norm function from the system Users input one vector Users press compute button Users get the result 3 2 3 Matrix Use Cases Use case 9 Matrices Addition Task Primary Actor Preconditions Process Result Adding two matrices Users Users choose the addition function from the system Users input two matrices Users press compute button Users get the result Use case 10 Matrices subtraction Task Primary Actor Preconditions Process Result Subtracting two matrices Users Users choose the subtraction function from the system Users input two matrices Users press compute button Users get the result Use case 11 Matrices Multiplication Task Primary Actor Preconditions Process Result Multiplying two matrices Users Users choose the multiplication function from the system Users input two matrices Users press com
25. and Result panels The user can easily to go to Vectors or Matrices created by clicking on their names The Vector or Matrices Creating Toolbar is used to create vectors or matrices The user define the size of a vector or matrix and number type in here The biggest part is used to let the users to input numbers into vectors and matrices The last one is the function toolbar which let the users to choose the functions to work on vectors or matrices 51 Linear Algebra System 5 6 Non functional Requirement Design 5 6 1 Minimise the scope of local variables By minimise the scope of local variables the readability and maintainability will increased 13 Fox example if one variable is only used in the for loop of one method in the middle of the whole class code but it is declared in the constructor then the scope for this variable is too big When people read the code before they really read the method using this variable they have already the variable s type and initial value Moreover if the program evolves and the variable is no long used it is easy to forget to remove the declaration of the variable So the best way for minimising the scope of local variable it is to declare it where it is first used 5 6 2 Error and Exception Handling Using Error and Exception Handling can increase the reliability and robustness of a program It can be achieved in two stages Stage one finding all possible errors and exceptions 1 W
26. and fields The entries are the number in a certain position of a vector or matrix The fields are vector and matrix So the system must have the function to recognise both entries and field from users input and then create an object in the system For different field calculation the system should output the result in different form Then the users can easily tell if the result is a vector or matrix Moreover the entries should also be presented in different form according to their number types 3 5 Error and Exception Handling The number type and data input and output are quite complicated it is easy to have errors and exception when the system running so in order to make the system robust it should has a strong error and exception handling functions Once the error or exception happen the system can catch it and pop up an error window Besides catching errors and exceptions it is more important to design the system in an error and exception preventing way to make the error and exception can not easily happen For example in case of the system using command line input when the users implement a calculation sometimes they will input the wrong command which may causes an error To prevent this we can set some calculation buttons in the user interface to let users to choose 3 6 Testing Requirement System Testing is to verify how well the system actually meets the original requirements Since this 36 Linear Algebra System
27. function needs to work with a scalar then input the scalar in the scalar text area this text area only accept the decimal number If the function needs to work with another vector or matrix choose the vector or matrix name from the combo box on the right of Compute With label Before doing that please make if the vector or matrix chosen is not empty Click Get Result button then the result panel will show the result Case 5 Clear the Result Panel 1 2 Click the File from the menubar Click Clear Result Panel Case 6 Close the Application 1 2 Click the File from the menubar Click Close 98
28. is a mathematical project the accuracy of computational outputs is the most important This requirement must be achieved in all three testing stages which are component testing system testing and acceptance testing In addition the logical inherence in linear algebra arithmetic is quite strong for example the matrices multiplication requires the calculation of matrices addition So it is not appropriate to start next component until the current one is completed and tested In the system testing stage the system integration shall be tested Since each linear algebra arithmetic component had been already tested in the previous stage the integration for this part would not be a problem The data input and output testing is the key in this level because they may belong to different types The acceptance testing needs to consider every circumstance that errors and mistake made by user lead to cause a problem 3 7 General Constraints 3 7 1 Operating System and Hardware Requirement The system is required to have a high compatibility Objective 4 which means it can run in different main Operating Systems like Windows XP Mac OS Unix and Linux Moreover the system should work on the recent five year computers 3 7 2 Programming Language Regarding to the scope of this project any main stream programming language can work well like C C and Java C and C all have memory allocation function to mange memory using However the deve
29. matrix name vector or matrix name current vector matrix with from the right bottom como box Click on the get result It doing the calculation It doing the calculation Pass button on the vector or matrix on the vector or matrix according to according to function chosen to function chosen to read the scalar read the scalar or selected vector or selected vector or matrix from matrix from the 75 Linear Algebra System combo box and shows the result in the result combo box and shows the result in the result panel panel Click the tabbed panel It shows the selected It shows the selected Pass panel panel Click File from menu It shows menu item in It shows menu item in Pass bar under File under File Click clear it menu It clear text in It clear the text in Pass item from File result panel result panel Click Quit The application The application Pass window closes window closes Input Testing Action Expected Result Actual Result Status Input right format of It creates the certain It creates the certain Pass number in the area of number of entries number of entries defining vectors and matrices size and click create button Input wrong format of It popup a Error It popup Error Pass number or nothing in Message Message the area of defining vectors and matrices
30. real Object Matrix or Vector The real Object and the function name Error Parameter The real Object and the function name The result _ There are two main stages in this model The one is from the beginning to Create an Object In this stage the system read the users input and transform them into an object form a matrix or a vector However if the input is not acceptable in the system the system will show an error message and terminate the process by sending an error parameter to the error function Then the system passes the object into the next stage In this stage after user choosing the function to implement on the object like calculating the determinant of the matrix the system will check if the function is valid on this object If it is not a valid function such as calculating the determinant of Linear Algebra System a 3 2 matrix the system shows an error message and terminate the process Or the system implements the function on the object and then returns the result 5 3 Object Oriented Design Object Oriented Design is about developing an object oriented model of a software system to reflecting the identified requirements It involves designing object classes and relationships between these classes Then these classes define objects in the system and the interaction between objects 5 3 1 Object Class Model The object class model is to encapsulate information in objects For every obj
31. size and click create button Input right format of It reads that scalar and It reads that scalar and Pass number in the Scalar use it in the function use it in the function area and implement the function Input wrong format of It popup a Error It popup Error Pass number or nothing in Message Message the Scalar area and implement the function Input right format of It reads entries and It reads entries and Pass number in entries of shows vector of shows vector of vectors of matrices matrices in the result matrices in the result and click confirm panel panel button Input wrong format of it pops up a error pops up a error Pass number or nothing in entries of vectors of click matrices and confirm button window window 76 Linear Algebra System 8 Conclusion In this part a general evaluation and critique about this project should be made It will also talk about how this project can be developed in the next stage 8 1 Evaluation and Critiques 8 1 1 Achievement Recalling the objectives of this project in the chapter one the work so far has finished most of them especially the primary objectives Capable of process different types of number such as decimal number rational number or complex number Capable of doing some general linear algebra arithmetic which is actually about vector and matrix operations Capable of imple
32. the cosine between two vectors Rationale This is the basic vector arithmetic Index 12 Name Norm Summary 1 User input the vector 2 Then the system outputs the norm of the vector Rationale This is the basic vector arithmetic 4 2 2 Matrix Functions Index 13 Name Matrices Addition Summary 1 User input two matrices 2 Then the system outputs sum of two matrices Rationale This is the basic matrix arithmetic Index 14 Name Matrices Subtraction Summary 1 User input two matrices 40 Linear Algebra System 2 Then the system outputs result of subtracting two matrices Rationale This is the basic matrix arithmetic Index 15 Name Matrices Multiplication Scalar Summary 1 User input one matrix and a scalar 2 Then the system outputs product of two matrices Rationale This is the basic matrix arithmetic Index 16 Name Matrices Multiplication Matrix Summary 3 User input two matrices 4 Then the system outputs product of two matrices Rationale This is the basic matrix arithmetic Index 17 Name Matrices Multiplication Strassen Algorithm Summary 1 User input two matrices 2 Then the system outputs product of two matrices by using Straseen Algorithm Rationale It is required from the objective of the project Index 18 Name Matrices Multiplication Coppersmith Winograd algorithm Summary 1 User
33. the field numerator and dominator to represent a and b They are all BigInteger type which can store long integers then int type Constructor Problems There are two problems need to be solved when initialising the Rational Number object The first one is the rational number input by the user is not factorised To solve this problem the system called the cancel to normalise the rational number The cancel is a method in the RationalNum class which uses the gcd method from BigInteger Class to find the greatest common divisor and 53 Linear Algebra System then divide the both numerator and dominator to get the factorised rational number form The second problem is to change the decimal number or integers into rational number form This is has been mention in the Literature Review Rational Number section 6 2 1 3 ComplexNum The complex number has the form of atbi where a and b are real numbers i is the imaginary unit In the system it uses realPart variable as a and imaginaryPart variable as b The type of realPart and imaginaryPart is both RationalNum The reason to do this is to make it easier to change DoubleNum object into ComplexNum object 6 2 2 Vector It uses a single FieldElement type array to store entries The Vector functions iterate on every FieldElement objects stored in it and call the objects operations For different Vector operations the system will call different
34. users a platform to write their own functions in the Matlab language which just will behaved just like the built in functions The working environment in Matlab is similar as in Maple It also use worksheet based interface It has separate Edit and Graphic windows to let user edit and save program and plot graphics The basic building block in Matlab is matrix and the fundamental data type is array By using the highly efficient algorithm from the LINPACK libraries Matlab is optimized for matrix and vector operations 9 There are many similar features between Matlab and Maple So the features overlapping with Maple can fit and be improved in my project will not be bothered Fitting Input output Matlab support interactive computation the user can input data in command window and the system show the result in the screen and the user can choose to input the data from file and output the result into a file e Data Type as mentioned before the fundamental data type is array There are several distinct data object can be created integers real numbers matrices strings structures and cells There is no need to declare the data type when creating a data object The system will categorise it automatically 10 e Command history it records commands executed in the command window The user can use up arrow to choose the previous commands Improving 28 Linear Algebra System e Strict working directory the file cannot be f
35. 12 1 4 14 9 12 And the adjoint is Adj A 3 7 1 1 6 8 2 3 4 4 Determinants relating to Inverse and Linear Equation Determinants and Inverse It was mentioned in the last section about how to calculate the inverse of an invertible matrix 20 Linear Algebra System However it is not an algebraic formula and it not appropriate to programme In here an algebraic formula to calculate the inverse will be presented Ifa square matrix A is non singular A is invertible and A IAA adj A Determinants and Systems of Linear Equations Theorem is a system of n linear equations with variables which has unique solution only if A 0 or has many or no solutions Cramer s Rule 5 If AX Y is a system of n linear equations with n variables and A 0 Then the solution is ANA is the matrix obtained by replace the i column of A with 2 3 5 Vector Spaces 2 3 5 1 Properties Vector Space R Definition R consists of the set of a sequence of n real numbers Fox example 1 4 3 5 is one of elements Definition u u u and v Vv v are two elements of They are equal when Un Vn Definition u uj Un and v vy v are two elements of and c is a scalar uty U vj Un Vn CUn Properties u v and w are vectors in R c and d are scalars lutv vt u 2 u vtw utv tw 3 u 0 0 u
36. 4 5 14 Pass 19 72 19 72 1 2 4 1 4 1 3 3 2 5 3 1 2 1 6 5 3 1 2 1 6 Pass 1 2 1 4 2 3 124 5 31 2 1 6 5 3 1 2 1 6 Pass 4 7 2 24613431971 57 431 32 161 574431 32 16i Pass 2 301 2 301 2 61 3 31 9 71 47 2 57 431 32 161 57 431 32 161 Pass 2 30i 2 301 1 2 1 4 2 3 2 61 3 31 9 71 1 4 1 4i 1 4 1 41 19 6 1 21 1 19 6 1 21 1 14i 2 i 4 1 2 1 4 2 3 1 4 1 41 1 4 1 41 19 6 1 21 1 19 6 1 21 1 Vector Distance Vector A Vector B Expected Result Actual Result Status 3 6 1 251 1 41421356 1 41421356 Pass 3 1 7 2 4 Error Message Error Message Pass 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 2 1 49341904 1 49341904 Pass 12 4 1 4 1 3 3 2 3 09681736 3 09681736 Pass 1 2 1 4 2 3 124 3 09681736 3 09681736 Pass 4 72 2 61 3 31 9 7i Error Message Error Message Pass 2 61 3 31 9 71 47 2 Error Message Error Message Pass 1 2 1 4 2 3 2 61 3 31 9 71 Error Message Error Message Pass 1 1 2 4 4 1 1 2 1 4 2 3 Error Message Error Message Pass Vector Cosine Vector A Vector B Expected Result Actual Result Status 3 6 1 2 5 1 0 99600651 0 99600651 Pass 3 1 7 2 4 Error Message Error Message Pass 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 2 1 5 10 2 8 10 8 1 5 1018 2 8 10 Pass 1 2 4 1 4 1 3 3 2 4 8 10 5 10 4 8 10 5 10
37. 7 2 246i 3431 97i 2 61 4431 7 7i 246i 4 31 Pass 7 71 2 61 3 31 9 7 4 7 2 2 6i 4 31 2 61 4 3i Pass 7 71 7 71 1 2 1 4 2 3 1 i 2 9 4 1 1 2i 7 4 V21i 7 4 1 Pass 10 341 10 3 1 1 i 2 i 4 i 1 2 1 4 2 3 1 2 i 7 4 1 21 7 4 Pass 10 3 1 10 341 Vector Multiplication Scalar Vector Scalar Expected Result Actual Result Status 3 2 11 5 15 10 55 15 10 55 Pass Null 2 Error Message Error Message Pass 5 2 8 3 20 7 2 5 1 16 3 40 7 5 1 16 3 40 7 Pass 246134319971 3 6 61 9 31 6 61 9 31 Pass 27 71 27 71 Vector Multiplication Dot Product Vector A Vector B Expected Result Actual Result Status 1 2 6 2 4 1 2 8 6 2 8 6 Pass 3 1 7 2 4 Error Message Error Message Pass 68 Linear Algebra System 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 2 1 12 3 6 12 14 1 12 3 6 12 14 Pass 12 4 1 2 1 4 2 3 1 2 1 2 8 3 1 2 1 2 8 3 Pass 1 2 1 4 2 3 12 4 1 2 7 4 10 3 1 2 7 4 10 3 Pass 4 7 2 24613431971 84241 21421i 8 24i 21 21 Pass 18 141 18 141 2 61 3 31 9 71 47 2 8 241 21 211 8 241 21 21 Pass 18 141 18 141 1 2 1 4 2 3 211 4 1 1 2 1 21 1 2 1 21 Pass 1 2 1 41 1 2 1 41 8 3 2 31 8
38. 79 Linear Algebra System 9 Bibliography 1 Courant R and Robbins H 1996 What is Mathematics Oxford Oxford University Press 2 Williams G 2005 Linear Algebra with Application 5 ed London Jones and Bartlett 3 Lay David C 1997 Linear Algebra and its Applications 2nd ed Harlow Addison Wsley 4 Grossman Stanley I 1994 Elementary Linear Algebra 5th en London Sauders College 5 Kolman Bernard Hill David R 2005 Introductory Linear Algebra an applied first course 8th ed N J Pearson Prentice Hall 6 Corman Thomas H 2001 Introduction to algorithms 2nd ed London MIT 7 WIKIPEDIA Coppersmith Winograd algorithm In Wikipedia the free encyclopedia online St Petersburg Florida Wikimedia Foundation Available from http en wikipedia org wiki Coppersmith Winograd algorithm Accessed 25 04 07 8 Richard D 2002 Advanced Mathematical Methods with Maple Ist ed Cambridge Cambridge Univsersity Press 9 Wilson Howard B 2002 Advanced Mathematics and Mechanics applications Using matlab 3rd ed London CRC 10 Pratap R 2006 Getting Started with Matlab Oxford Oxford University Press 11 Sommerville I 2004 Software Engineering 7th ed London Addison Wesley 12 WIKIPEDIA Determinant In Wikipedia the free encyclopedia online St Petersburg Florida Wikimedia Foundation Available from http en wikipedia org wiki Determinant Accessed 27 04 07 13 Bloch J 2001 Effectiv
39. Counter if diagonalEntry isZero search for non zero entry boolean found false for int candidate row 1 candidate lt tmp getRows candidate t if tmp get candidate colCounter isZero tmp swapRows row candidate found true break if found if colCounter tmp getCols return tmp continue else diagonalEntry tmp get row colCounter 82 Linear Algebra System for int j colCounter j lt tmp getCols j FieldElement oldEntry tmp get row 3 tmp set row j oldEntry divide diagonalEntry for int j 1 lt tmp getRows j FieldElement factor tmp get j colCounter if row j factor isZero continue for int k colCounter k lt tmp getCols k FieldElement oldEntry tmp get j tmp set j oldEntry subtract tmp get row k multiply factor return tmp Returns a matrix that is this Matrix with Gauss elimination executed on In other words It returns a row echelon form of this Matrix return matrix in row echelon form 7 public Matrix gausselim Matrix tmp this copy int minOfRowsCols Math min tmp getRows tmp getCols int colCounter 0 int row 0 while row lt minOfRowsCols amp amp colCounter lt tmp getCols rowrr colCounterrr 83 Linear Algebra
40. It makes the method only check the entries above the diagonals isUpperTriangular The method to check upper triangle is similar to check for lower triangle The only difference is the code in the second for loop is like this for int j 1 j this numOfCols i 1 j if this get 1 j isZero So the postcondition for j is decrement every time the loop repeats Then the method will only check the entries below the diagonals getRow getColumn The method getRow int or getColumn int returns a new Vector object with the same entries as the ith row or column of a Matrix 56 Linear Algebra System Swapping rows or columns swapRows swapColumns The function of swapping rows or columns in a matrix swaps two rows or columns indices So this is done by calling getRow of getColumn to get ith row or column and store it in a temporary vector variable Then it gets jth row or column and set this row or column as ith row or column and set the temporary vector as the jth row or column 6 2 3 2 Second Level The functions in this level are multiplication Gaussian elimination and Gauss Jordan Reduction Multiplication Coding the standard multiplication function is actually simple It is just about using for loop to find the corresponding entries and multiply the FieldElement objects on those entries and the return new FieldElement objects for the entries in the new matrix This method is from MatrixMultiplica
41. Linear Algebra System Kun Wang Batchelor of Science in Computer Information System with Honours The University of Bath May 2007 Linear Algebra System This dissertation may be made available for consultation within the University Library and may be photocopied or lent to other libraries for the purposes of consultation Signed Linear Algebra System Linear Algebra System Submitted by Kun Wang COPYRIGHT Attention is drawn to the fact that copyright of this dissertation rests with its author The Intellectual Property Rights of the products produced as part of the project belong to the University of Bath see http www bath ac uk ordinances intelprop This copy of the dissertation has been supplied on condition that anyone who consults it is understood to recognise that its copyright rests with its author and that no quotation from the dissertation and no information derived from it may be published without the prior written consent of the author Declaration This dissertation is submitted to the University of Bath in accordance with the requirements of the degree of Batchelor of Science in the Department of Computer Science No portion of the work in this dissertation has been submitted in support of an application for any other degree or qualification of this or any other university or institution of learning Except where specifcally acknowledged it is the work of the author Signed Linear Algebra System Abstr
42. act This Linear Algebra System is a Java Code written application which is equipped with functions of solving Linear Algebra related computation by implementing mathematical algorithms It is concerned with the manipulation and arithmetic of arbitrary sized vectors and matrices It can work with decimal number rational number and complex number Besides using the normal linear algebra algorithms it also delivers functions employing some advanced algorithms with low complexity A basic neat Artificial Intelligence is programmed in order to improve the performance Linear Algebra System TO MUCHO osc side ati 8 Literature 9 2 1 9 22 este ru io du Eg ed dL GU NF DN fetes 9 22 1 Rational Number 9 2 2 2 Complex 10 2 3 Linear ATgebra editrice tees ne eese esten eee pide stein 11 2 3 1 Matrices and Linear Equations essere 11 2 3 2 Matrix Operation y DG 16 2 3 3 Algebraic Properties of Matrix 17 2 3 4 Determinants of Square 0 eee 19 2 38 Mere lE 21 24 Advanced 23 2 4 1 24 2 4 2 Strassen Algorithm 24 2 4 3
43. anged by rows and columns We call each number in the array the element of such matrix However in this dissertation the entry has also been used to describe the element of a matrix In Linear Algebra we focus on the large system of n linear equations with n variables represented by matrices So before illustrating how matrices work on the system of linear equation there are some terminologies about a matrix that should be aware of 2 3 1 4 Matrices Properties Rows and Columns 2 5 8 there are 6 1 A matrix can be decomposed into Rows or Columns For this matrix A two rows and three columns in it The first row is 2 5 8 and the second row is o o or o c Linear Algebra System 2 415 2 8 The first column is 6 the second is and the third is 7 Location The location of an element in a matrix is decided by giving row and column of that element In the previous example matrix A the number in Row and Column 2 is 5 represented in location 1 2 Submatrix A submatrix is a part of a given matrix which is generated by removing certain rows and columns of certain location of the matrix 2 5 8 6 1 For example in the matrix its submatrices can be Size and Type The size of a matrix is described in form of axb which a is the number of rows and b is the number of column For matrix A it is 2X 3 matrix There are three types of matrix square matrix in which the num
44. ber of rows and column are same row matrix in which there is only one row and column matrix in which there is only one column matrix 2 5 8 6 1 7 6 1 7 430 Square Matrix Row Matrix Column Matrix Identity Matrices An identity matrix is a square matrix with Is in the diagonal locations and zeros elsewhere 1 0 0 E 1 L A h 0 1 0 xampie 0 1 3 0 0 1 Triangular Matrices Linear Algebra System A triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero A matrix 0 bi lap lai ln 2 ad is called lower triangular matrix or left triangular matrix and analogously a matrix of Un U13 Uin U22 U23 Un U Un 1 n 0 Unn is called upper triangular matrix or right triangular matrix Row Echelon Form The matrix in row echelon form is actually upper triangular matrix It must is satisfies the following requirements All nonzero rows are above any rows of all zeroes The leading coefficient of a row is always strictly to the right of the leading coefficient of the row above it For example 9 3 5 9 3 5 004 and O O 4 0 O 0 0 O 0 The leading coefficient of a row in a matrix is the first nonzero entry in that row Every matrix can be transformed into a Row Echelon form by using Gaussian elimination It employs elementary operation which Given a matrix with rows Ry R2 R the following are the th
45. bility of algorithms and the inherent difficulty in providing scalable algorithms for specific computational problems In other word it s about how the running time and memory requirements of algorithm change as the size of input to an algorithm increases So if an algorithm fails to scale well no matter how far the computing technology improved this algorithm is not applicable in industry Time Complexity Complexity is a measure of how effective an algorithm is There are many different ways to calculate the effectiveness of an algorithm However one of the most important ways is to compute its time complexity The time complexity of an algorithm is the number of steps it takes to get the output For different length of input it may go through different number of steps to get the output It is not realistic to analyse every time complexity for different instances So we are only interest into rough calculations to get the time complexity eg n and n n would be the same This concept is called Asymptotic notations Big O the notations and are most usual notations to describe the asymptotic behavior of functions 2 4 2 Strassen Algorithm In mid sixties Volker Strassen developed the standard matrix multiplication algorithm In his algorithm named Strassen Algorithm there are three steps to multiply matrices A and B with both n n dimension to get matrix C with n n dimension Divide the input matrices A and B into n 2 n 2 sub mat
46. by the users mistake Code independency is quite strong in this system For so classes they can be used for other system without any change They should be quite easy to maintain and update 8 1 2 Critiques There are still some problems in this project 1 The Blockwise algorithm does not work properly in this project 2 Artificial Intelligence in this project is only designed on calculating the matrix determinant There are a lot of aspects of AI in linear algebra have not been concerned 3 Although the system achieved the interface simplicity it limits the function of the system Moreover interface layout still has problem When input a large matrix the entries are not structurally sorted out in the application window 4 It should have a array to store vectors or matrices Then the system work on more than two vectors or matrices 5 Error handling is too simple There are only two classes created For most errors they also use InvalidOperationException This categorising method is too general 6 The code coupling is a problem To implement one function it calls several methods This will badly affect maintainability 7 There are too many duplicated codes in the interface LAS class and there is only one class to support the user interface which is not ideal 8 System testing is not refined enough There are still a lot of aspects need to be tested 8 2 Further Development 8 2 1 Numbers Developing the system t
47. ce relating way But for some content like the requirement operating system hardware and interface they will not be mentioned in here because they have already discussed enough in the previous chapter and the on 4 2 Functional Requirements They are about what functions and service the system should provide It may involve the calculations technical details data manipulation and processing and other specific functionality that show how the use cases are to be satisfied In this project the functional requirement is relating to the linear algebra arithmetic which has two streams vector calculation and matrix calculation 4 2 1 Vector Functions Index 1 Vector Addition Scalar Summary 1 User input the vector and scalar 2 Then the system outputs the result of adding a vector to a scalar Rationale This is the basic vector arithmetic Index 2 Name Vectors Addition Vectors Summary 1 User input two vector 2 Then the system outputs the result of adding a vector to another vector Rationale This is the basic vector arithmetic 38 Linear Algebra System Index 3 Name Vector Subtraction Scalar Summary 1 User input the vector and scalar 2 Then the system outputs the result of subtracting a vector to a scalar Rationale This is the basic vector arithmetic Index 4 Name Vectors Subtraction Vectors
48. d blockWiseInverse from MatrixInverse class The det straOriginal CopperWinograd and blockWiselnverse will be discussed in the next session inverse This method is to calculate the inverse of a matrix This method calls the simple method from MatrixInverse class The algorithm using in simple is the standard algorithm to calculating the inverse of the matrix which is adding a identity matrix at the back of the matrix first and find the reduced echelon form of that matrix then the last a few columns of the matrix is the inverse of the original matrix However the actual implementation is a little bit different from the algorithm It uses two temporary matrices tmp and tmp representing the original matrix and the inverse Then it calculated the reduced row echelon form for tmp For every row operations during this process it also works on tmp2 to makes tmp and tmp2 like one matrix After finishing this the system checks tmp to see if it is an identity matrix If it is tmp2 is the inverse of the original matrix If not the method returns null code can be seen in appendix A Although this method does not call the gaussjord method to calculating the reduced row echelon form because of concerning doing the row operations in two matrices the procedure is same The way to test if the tmp is a identity matrix is to check if the diagonal entries are all equal to one rank This method is to calculate the rank of th
49. diagonal row in the following in which non diagonal entry in It can be done by multiply non diagonal rows by factors which is resulted from diagonal entry by non diagonal entries To make the non diagonal entries zero it use diagonal row to subtract the non diagonal rows and set the returned result as the new entries in the corresponding index in non diagonal rows for int j row j lt tmp getRows j 58 Linear Algebra System FieldElement factor tmp get j colCounter divide diagonalEntry if row j factor isZero continue for int k colCounter k lt tmp getCols k FieldElement oldEntry tmp get j tmp set j oldEntry subtract factor multiply tmp get row k The first for is factoring the diagonal row The second for is factoring non diagonal rows and then operate on the non diagonal rows to make the non diagonal entries zero 3 After finishing the first diagonal go to the next diagonal and repeat and 2 Gauss Jordan Reduction gaussjord It is quite similar as Gaussian Elimination but get the reduced row echelon form The only difference is the step 2 Step 2 for this After finding the non zero diagonal it implements the row operations to make the diagonal one and the entries denoted as non diagonal entry in the following with same column index zero To make the diagonal one in other word of factorising the row it can b
50. e Java programming language guide London Addison Wesley 80 Linear Algebra System 10 Appendix A Matrix Class package Backend public class Matrix public FieldElement det if this isSquare return null if this isLowerTriangular this isUpperTriangular FieldElement det new DoubleNum l for int row 1 row lt this getRows det det multiply this get row row return det for int i 1 i this getCols i if this isZeroCol i return new DoubleNunm 0 for int i 1 i lt this getRows i t if this isZeroRow 1 return new DoubleNunm 0 Matrix tmp this gausselim FieldElement determinant tmp get 1 1 one for int row 1 row lt tmp getRows rowrr determinant determinant multiply tmp get row return determinant 81 row Linear Algebra System Returns a matrix that is this Matrix with the Gauss Jordan algorithm executed on In other words It returns the reduced row echelon form of this Matrix return matrix in reduced row echelon form public Matrix gaussjord Matrix tmp this copy int minOfRowsCols Math min tmp getRows tmp getCols int colCounter 0 int row 0 while row lt minOfRowsCols amp amp colCounter lt tmp getCols rowt t colCounter FieldElement diagonalEntry tmp get row col
51. e can go through each use cases to find all possible circumstance of users make a mistake to case the errors and exceptions 2 Analysing the relation between objects and their functions to check if they conflicts with each other 3 Since the objects in this system are all related with each other The attribute of one object is same for itself but maybe dangerous for others So does the functions We need to find these potential problem Stage two handling these errors and exceptions Besides using exception package in Java Api Library we also need to create some new exception objects Then we catch these exceptions from where the system calls the functions which are possible to cause the errors and exceptions This will be discussed in detail in Implementation 6 Implementation 6 1 Introduction This chapter is about how the design is actually implemented In other words it illustrates how the developer writes the program to reflect the requirements It also includes some specific problems and solutions happened in the process of coding The structure of this chapter will basically follow the object class model to discuss how these objects implemented both in high level discussion and some code explained in detail 52 Linear Algebra System 6 2 Number Structure and General Functions The number here does not only mean the decimal rational and complex number It also involves the vector and matrix which is the basic number of Li
52. e done by divide the entries in this row denoted as diagonal row in the following by the value of this diagonal To make the non diagonal entries zero it is done by multiplying the diagonal row by the non diagonal entires and then using diagonal row to subtract the other non diagonal rows for int j colCounter j lt tmp getCols j FieldElement oldEntry tmp get row 3 tmp set row j oldEntry divide diagonalEntry for int j 1 j lt tmp getRows j FieldElement factor tmp get j colCounter if row j factor isZero continue for int k colCounter k lt tmp getCols k I FieldElement oldEntry tmp get j k tmp set j k oldEntry subtract tmp get row 59 Linear Algebra System k multiply factor There are two differences in code comparing with gausselim One is that it factorise the diagonal row in the first for loop The second difference is in the second for loop 4 counts from 1 and the 4 counts from row which is the current row number So the So gausselim only changes the entries below the diagonal with the same column index to zero gaussjord changes all entries with the same column index as the diagonal 6 2 3 3 Third Level There are six functions in this level which are det inverse rank from Matrix class and straOriginal CopperWinograd from MatrixMultiplication class an
53. e matrix It firstly calls gausslim to find the row echelon form of the matrix Then the number of not full rows of zeros is the rank of this matrix 60 Linear Algebra System 6 3 Advanced Algorithms and Al The section is about how the advanced algorithms and AI design is implemented in this project and the problems happened when implementing them 6 3 1 straOriginal This method from MatrixMultiplication class reflects the Strassen Algorithm to multiply two matrices There is one pre condition to use this algorithm which is that the dimension of two matrices must in for of 2 2 The method first evenly divides the matrix into a 2 2 matrix entries are the sub matrix of the original matrix So if the method is used recursively the matrix can be divided into n 1 levels of 2 2 submatrices then by applying the multiplication and addition between submatrices the result can be calculated In the smallest submatrices there will be just a single number In that case matrix multiplication becomes number addition and multiplication However in the real work 2 2 is limited So the algorithm in this method does not exactly follow the original algorithm The pre condition for this method is that the two matrices must have the form of 2n 2n where n can be any integers The method will keep on dividing the matrix and submatrices into equal dimension submatrices until it is not dividable and then use matrix additions and standard mul
54. e of its rows or columns and their cofactors ith row expansion Al a Cii ai ith column expansion A 2a Ci ao tag Example 2 3 4 2 Properties of Determinants Definition if A 0 then the matrix A is singular or it s non singular Let A be a n n matrix and c be a nonzero scalar 1 If B cA then B c A 2 is the matrix after A interchanging two rows B A 3 IfB is the matrix after A adding a multiple of one row column to another row column then B A 4 5 6 A A 7 8 If elements in one row or column of square matrix A are all zeros det A 0 9 If ith row or the jth column of A is multiplied by a scalar c the det A is multiplied by c That is If we call this new matrix B then det B c det A 19 Linear Algebra System 10 If A has two equal rows of columns then det A 0 11 If one row column of A is a scalar multiple of another row column the det A 0 12 the determinant of a triangular matrix is the product of its diagonals 4 2 3 4 3 Determinants Definition The matrix formed by the cofactors Cj of given matrix A is called the matrix of cofactor of A The transpose of this matrix is called the adjoint of A adj A Example 2 3 A 1 4 2 1 3 5 0 3 2 3 2 0 31 2 C32 1 C33 4 4 2 sj ad 1 4 14 3 1 Then the matrix of cofactors of Ais 9 7 6
55. ect it has attributes and functions In programming language the objects are represented in the forms of classes There are four different groups of classes in this project FieldElement is the entries in vectors and matrices Field is referring to vectors and matrices Operators is about this operations on FieldElements Advanced algorithms reflect the advanced algorithms mentioned in the requirement The object class is represented as a named rectangle with two sections which are the attributes and methods from top to bottom It is using inheritance hierarchy to show the relationship between classes in the same group The child class inherits attributes and methods from the parent class FieldElement 46 Linear Algebra System As it is required in the Data Structure in Requirement Analysis section the project should work on three different types of number as input and output So the system uses DoubleNum RationaNum and ComplexNum to represent three types of number which are decimal number rational number and complex number respectively Since rational number is in the form of a b which a and b are any integers the numerator as a and dominator as b are defined in RationalNum class The complex number is in the form of a b i so realPart as a and imaginaryPart as b are defined in the complexNum The methods defined in this model are all some general mathematic arithmetic like additi
56. enOriginal a21 subtract all bll add bl2 strassenOriginal al2 subtract a22 b21 add b22 println pl n Matrix cll pl add p4 subtract add 7 Matrix 12 p3 add p5 Matrix c21 p2 add p4 Matrix c22 pl add p3 subtract p2 FieldElement cllEntries cll getEntries FieldElement cl2bEntries cl2 getEntries FieldElement c2lEntries c2l getEntries FieldElement c22Entries c22 getEntries FieldElement cEntries new FieldElement ml getRows m2 getCols for int i 0 i lt cll getRows i for int j 0 j lt cll getCols j cEntries i j cllEntries i j System out println cEntries cEntries n for int i 0 i lt cl2 getRows i int offset splitIndex for int j 0 j lt cl2 getCols j cEntries i j splitIndex cl2Entries i j 93 Linear Algebra System for int i 0 i lt c21 getRows i int offset splitIndex for int j 0 j lt c21 getCols j cEntries i splitIndex j c21Entries i jl for int i 0 i lt c22 getRows i int offset splitIndex for int j 0 j lt c22 getCols j cEntries i splitIndex j splitIndex c22bEntries i jl return new Matrix cEntries return simple ml m2 The Algorithm of Coppersmith Winograd for matrix multiplication
57. er tmp getCols return null Because there is no inverse of m row continue else diagonalEntry tmp get row colCounter for int j 1 j lt tmp getCols j FieldElement oldEntry tmp get row 3 FieldElement oldEntry2 tmp2 get row j tmp set row j oldEntry divide diagonalEntry tmp2 set row j oldEntry2 divide diagonalEntry for int j 1 j lt tmp getRows j FieldElement factor tmp get j colCounter if row j factor isZero continue for int k 1 k lt tmp getCols k FieldElement oldEntry tmp get j 87 Linear Algebra System FieldElement oldEntry2 tmp2 get j k tmp set j k oldEntry subtract tmp get row k multiply factor tmp2 set j k oldEntry2 subtract tmp2 get row k multiply factor boolean is false for int i 1 j 1 i lt tmp getRows amp amp j lt tmp getCols it j if tmp get j isOne 1 is true else break if is return tmp2 return null public static Matrix blockWiseInverse Matrix if checkSingular m return null if m getRows 1 return m if m getRows m getCols return null Matrix mTranspose m transpose tmpl is used to calculate the product of the inverse of A tran multiplied by A
58. ering AI in this project is that there is always more than one method when doing calculations on matrices and for matrices with different characteristic one method could take less time then others 2 0 0 For example the matrix A 3 1 0 which the determinant is 14 4 8 7 Either using the standard algorithm or Strassen Algorithm will take more than ten steps to get the result However for mathematicians they would recognise that this matrix is actually a lower triangular matrix which the determinant is just the product of diagonal entries 2 1 7 14 This only takes several steps In this project the AI technology will used to calculate the determinant of the matrix It can be developed in two ways The first one is to recognise the matrix form As what is mentioned in the literature review if the matrix is in triangular form then the determinant for this matrix is just the product of its diagonal entries So there are two steps to implement 1 Analysing the matrix form 2 Calculate the product of its diagonal entries if it is the triangular matrix The Second one is to analyse the characteristic of the matrix If a matrix has a row or column with several zeros it will be easier to use that row or column entries to multiply with cofactors because the product of multiplying zero and a cofactor is zero So the steps to implement this AI are 1 Analysing the matrix and find a row or column with more zeros 2 use that row o
59. ime Constraints ierit 37 3 7 4 Users of the 38 Requirement SpeclflCatllonDo FEE HRS GERENS HER 38 4 1 D CP 38 Linear Algebra System 4 2 Functional Requirements 38 4 2 1 Vector FUNCtIONS cccccccscccesecsscecseseeeeseeceseecsseecsseecseaeeseaeeesseessseeeneeeseseneeeeeaes 38 4 2 2 Matrix 40 4 2 3 Other cwn le 43 4 3 Non Functional Requirements 0 2 22 22 2 120011 1 000000000000000000000000000000 43 Syste DESIGN I D P 44 5 1 TtroductiOn c sccsccsssesecesssseecnssoneeonecoseeessonecogecagesagecanecanscanesarsansednecanssatesanseaneeanecanensante 44 5 2 System Models 44 5 2 1 Data Flow Model ins 44 5 3 Object Oriented 46 5 3 1 Object Class tette rerit en 46 5 3 2 Class Association Model 50 eae 50 5 5 User Interface 51 5 6 Non functional Requirement Design enne nene 52 5 6 1 Minimise the scope of local 52 5 6 2 Error and Exception 1 2000
60. in a efficient manner Rationale The scope for this project is still small comparing to other maths tools and the functions concerning in this project is narrow So the system might be updated in the future This is also from the secondary objectives Index 30 43 Linear Algebra System Name Ease of use Summary It should have a friendly user interface User do not even need to read the guideline to use it Rationale Because this project is designed for the users who want to do some simple linear algebra calculations but do not spend hours to figure out how to use matlab or maple So the friendly user interface is very necessary 5 System Design 5 1 Introduction The system design is the most important part of a software development process which decides the logical organisation of the software The easiest way to illustrate it is to use models in UML language The models using in this part are System Models and Software Models 5 2 System Models The system models are about representing users requirement in a technical way For different models they focus on the different perspectives of the system design Considering the system itself the most important models are Data Flow Model which shows how data is processed 5 2 1 Data Flow Model 44 Linear Algebra System Access to System The original Data Entries Number and Error Parameter Field Type The
61. input two matrices 2 Then the system outputs product of two matrices by using Coppersmith Winograd algorithm Rationale It is required from the objective of the project Index 19 Name Gaussian Elimination Summary 1 User input the matrix 2 Then the system outputs the Row Echelon Form of this matrix Rationale This is the basic matrix arithmetic and also be used for other functions Index 20 41 Linear Algebra System Name Gauss Jordan Reduction Summary 1 User input the matrix 2 Then the system outputs the Reduced Row Echelon Form of this matrix Rationale This is the basic matrix arithmetic and also be used for other functions Index 21 Name Determinant Summary 1 User input the matrix 2 Then the system outputs the determinant of this matrix Rationale This is the basic matrix arithmetic Index 22 Name Rank Summary 1 User input the matrix 2 Then the system outputs the Rank of this matrix Rationale This is the basic matrix arithmetic Index 23 Name Matrix Inverse Summary 1 User input the matrix 2 Then the system outputs the inverse of this matrix Rationale This is the basic matrix arithmetic Index 24 Name Matrix Inverse Blockwise Summary 1 User input the matrix 2 Then the system outputs the inverse of this matrix Rationale This is required Index 29 Summary 1 User input the matrix 2 Then the system
62. into a low triangular by calling gausselim method Detailed code can be seen in the Appendix A 6 4 User Interface The layout of each component is like the draft layout in the Design part When the users want to create a vector or matrix they need to input the dimension of matrix first and then choose the number type they want to enter After clicking the create button there will be a certain number of empty TextField created in the middle panel Those are the entries of the matrix Entries Layout For different number type the layout of the entries will be different because DoubleNum only needs one value to initialise but the other two need two values which are the numerator and the dominator for rational number and imaginary and real part for complex number When creating rationalNum entries in order to make the users clear about which entry refers to the numerator of a rational number and which entry refers to the dominator of a rational number the system will put a between the numerator and dominator and put every single number in a bracket Code 7 63 Linear A Igebra System if tp equals Rational Number JTextFiel ld numeratorEntries new JTextField 3 JTextField denominatorEntries new JTextField 3 JLabe slash new JLabel JLabel leftBra new JLabel JLabel rightBra new JLabel add add add J
63. is the matrix is double array which means getting entries need an extra pair of indices For example Transpose public Matrix transpose Matrix tmp new Matrix this getCols this getRows for int row 1 row lt this getRows rowrr 55 Linear Algebra System for int col 1 col lt this getCols 1 tmp set col row this get row col return tmp There is a temporary matrix tmp defined in this method It is using two for loops to get every entry and set the entry in the ith row and jth column in the original matrix to the jth row and ith column by invoking this line of code tmp set col row this get row col isLowerTriangular This function was a little bit tricky to code Firstly if the certain entry is not zero as expected then the whole process can stop no matter loop is still on the way Secondly there is no need to check every entry but only the entries above the diagonals The first problem is solved by a if else statement If the certain entry is not zero the method go to else statement and returns false to shut down the loop for int i l i lt this numOfRows irr for int j i 1l j lt this numOfCols 144 if this get 1 j isZero else return false The second one is solved by set the value of j in the second for loop equal to 1 1 Then for every time the outer for loop recurs and i increments j counts from i 1
64. loper would prefer using Java to write the program It is because firstly considering the scale of the project it will only occupy a big amount of memory Secondly java has decent and easy to use graphic package to fulfil the requirements on the system interface Thirdly the Java Virtual Machine will ensure the compatibility of the system since there are few operating systems cannot run JVM 3 7 3 Time Constraints This is one term project But actually most of the core works started from the second semester and in the meanwhile there are other courses and project to work on So there is actually not too much time So it could happen that some requirements will not be achieved finally 37 Linear Algebra System 3 7 4 Users of the system The users for this project should be students or others who just want to implement some quick calculation on vectors or matrices rather than some professionals who want to do some complicated operations 4 Requirement Specification 4 1 Introduction The requirement specification focuses on both user and system requirement It can be seen as an advanced stage developed from requirement analysis which summarise the requirements and then represent them in a more design like form In other word it is the bridge between gathering user s need and telling the developer what exactly need to be designed and implemented So it may repeat the same content which has been mentioned before but in a more practi
65. low Two fractions are multiplies as follow ac ac bd bd Additive and multiplicative inverse exist in the rational numbers 1 2 if bz0 b b b b a It follows that the quotient of two fractions is given by a c ad b d bc 2 2 2 Complex Number The process which first requires the use of complex number is that of solving quadratic equations The equation has no real solution since the square of any real number is never negative So we have to extend the concept of number by introducing numbers that will make the equation solvable Then people introduced the symbol i by defining i 1 and complex number In mathematics a complex number is a number of the form a bi where a and b are real numbers and i is the imaginary unit with the property i 1 the real number 10 Linear Algebra System a is called real part and b is called imaginary part Arithmetic Addition a bi c di a c b d i Subtraction a bi c di a c b d i Multiplication a bi c di ac bci adi bdi ac bd be ad i a bi a bi c di _ ac bd bce ad i c di c di c di eed Division 2 3 Linear Algebra In this section I will establish the knowledge of Linear Algebra based on the objectives of the project 2 3 1 Matrices and Linear Equations Linear Equations are equations with variables in them such as x 2y 7 A matrix is a rectangular array of numbers arr
66. lt Actual Result Status 3 5 5 489 1 3 4 j 440241 92 9 8 3 21 8 T T 7 7 x 824 6 3 11 2 1 7 2 1 7 3 5 5 1 4 2 Error Message Error Message Pass 8 3 2 4 5 5 Null Error Message Error Message Pass 3 4 Multiplication Scalar 71 Linear Algebra System Matrix A Scalar Expected Result Actual Result Status 3 5 5 9 15 I5 9 15 315 Pes 9 8 3 27 24 9 27 24 9 8 2 4 24 6 12 24 6 12 3 5 5 null Error Message Error Message Pass 9 8 3 8 2 4 Matrix Multiplication Strassen Algorithm Matrix A Matrix B Expected Result Actual Result Status 2 4 11 4 2 4 11 4 97 468 95 233 97 468 95 233 Pass 6 16 14 6 16 7 14 255 658 241 367 255 658 241 367 3 32 15 3 32 3 15 342 785 311 520 342 785 311 520 9 11 1 D 11 3 1 102 319 188 236 102 319 188 236 2 4 11 4 1 4 2 Error Message Error Message Pass 6 16 7 14 3 32 3 15 9 11 3 1 3 5 5 Null Error Message Error Message Pass 9 8 3 8 24 Matrix Multiplication Coppersmith Winograd Algorithm Matrix A Matrix B Expected Result Actual Result Status 2 4 11 4 2 4 11 4 97 468 95 233 97 468 95 233 Pass 6 16 7 14 6 16 7 14 255 658 241 367 255 658 241 367 3 32 3 15 3 32 3 15 342 785 311 520 342 785 311 520 9 11 3 d 9 11 3 d 102 319 188 236 102 319 188 236 72 Linear Algebra System
67. matrix addition function from the system Process Users input two vectors 30 Result Linear Algebra System Users press compute button Users get the result Use case 2 Vectors Subtraction Task Primary Actor Preconditions Process Result Subtracting two vectors Users Users choose the vector subtraction function from the system Users input two vectors Users press compute button Users get the result Use case 3 Vectors multiplication Task Primary Actor Preconditions Process Result Multiplying two vectors Users Users choose the vector multiplication function from the system Users input two vectors Users press compute button Users get the result Use case 4 Vectors dot product Task Primary Actor Preconditions Process Result Calculating the dot product of two vectors Users Users choose the dot product function from the system Users input two vectors Users press compute button Users get the result Use case 5 Vectors cross product Task Primary Actor Preconditions Process Result Use case 6 Vectors Cosine Task Primary Actor Preconditions Process Result Use case 7 Vectors distance Calculating the cross product of two vectors Users Users choose the cross product function from the system Users input two vectors Users press compute button Users get the result Calculating the cosine of two vectors
68. menting some advanced math algorithms with low complexity to do matrix calculations Firstly the system can work on three types of number which are Decimal Number Rational Number in form of a b and Complex Number Each type of numbers has its own functions and they can also work together Secondly the system can do 30 different calculations It covers most normal linear algebra arithmetic in vector and matrix area Functions required in Requirement all have been completed There are three advanced algorithm implemented The two for multiplication passed the testing The one for matrix inverse does not work properly The code implementation exactly follows the theory in the Literature Review but the output is wrong So the problem could be the misunderstanding of that algorithm in the early stage or the algorithm can only work on some certain situations Secondary Objectives Artificial Intelligence Friendly user interface Robust system with error handling functions Independent code structure working on different fields which can make the system easy to improve and develop later Artificial Intelligence has applied in calculating the determinant of the matrix The user interface of the system is simple to follow The users do not need to read the user manual to start using the system 77 Linear Algebra System The error handling functions in this system can handle most common errors and exceptions caused
69. n infinite decimal representation A rational number is a number which can be expressed as a ratio of two integers Non integer rational numbers commonly called fractions are usually written as the vulgar fraction a b where b is not zero and a is called numerator and b is called dominator A rational number can be represented in an infinite form like 1 2 2 4 3 6 So normally the rational number is simplified into the form which the numerator and dominator have no common Linear Algebra System divisor exception 1 The biggest common divisor between the numerator and dominator is called the greatest common division which is used to factorize the rational number into the simplest form The decimal expression with finite decimal digits is a special form a rational number such as 1 44393 42894 420098 They can change back to the normal form of rational number The normal method is to multiply it by 10 and set it as a numerator and set 10 as a dominator where n is the number of its decimal digits Then we factorise it into the simplest form However change the normal form rational number to a decimal number may change the number into other type of decimal number with infinite decimal digits For example 1 3 is a rational number if change it into a decimal expression it will become 1 33333 with repeating 3 Arithmetic Two rational number a b and c d are equal if and only if ad bc Two fractions added as fol
70. nces classifiers if shiny then diamond and controllers if shiny then pick up In Linear Algebra there are usually more than more one ways to do calculations on a matrix so for different form of matrices there should be a better way to compute rather than others Concerning with the project it is possible to equip AI in this system to make the system think and then solve the problems like a mathematician 2 5 Current System In this section I will discuss two of current mathematics system Maple and Matlab The reason of choosing these two is their Mathematical functionality flexibility and the specialty on Linear Algebra By researching and analysing the current system and recalling to the aim of my system some techniques of the current systems can be inherited and improved in my project 2 5 1 Maple Maple is a Symbolic Computation System or Computer Algebra System providing the user interface to allow users to input mathematics in traditional mathematical notation It is equipped with tools of solving many mathematical problem including integrals systems of equations differential equation and problems in linear algebra Moreover graphics support is Maple s another specialty The user can use its graphics routines for visualizing mathematical problem Maple is worksheet based graphical interface The user can choose worksheet or command line to access calling functions So the user can edit the worksheet file in c
71. ncludes some different methods of multiplying two matrices The standard method of the Matrix class is the school method All the other stuff is to be considered experimental stuff public class MatrixMultiplication private static int STRASSEN_ORIGINAL_TRUNCATION_POINT 48 private static int STRASSEN_WINOGRAD_TRUNCATION_POINT 48 private static void checkDimensions Matrix ml Matrix m2 throws InvalidOperationException if ml getCols m2 getRows throw new InvalidOperationException Tried to multiply a matrix with ml getCols columns and matrix with m2 getRows rows private static boolean checkSize Matrix ml Matrix m2 if ml getCols 2 0 ml getRows ml getCols return false return true Uses the standard method for multiplication of Matrix objects Asymptotic runtime 0 3 param ml param m2 return ml multiplied by m2 91 Linear Algebra System throws InvalidOperationException amp public static Matrix simple Matrix ml Matrix m2 throws InvalidOperationException checkDimensions ml m2 int resultRows ml getRows int resultCols m2 getCols Matrix resultMatrix new Matrix resultRows resultCols for int i 1 i lt resultRows itt for int j 1 j lt resultCols j resultMatrix set i 3 ml getRow i multi
72. near Algebra For different types of number there are some different functions This section will talk about three main number types which are FieldElement Vector and Matrix and their functions 6 2 1 FieldElement FielddElement is the actual value of entries in vectors or matrices It is the super class of other types of number which are DoubleNum RationalNum ComplexNum Some basic methods need to be defined in this class However the arithmetic is different from these three numbers So most methods will be empty which only give a basic structure for subclasses Because different types of number have different attributes and use different arithmetic there will be a problem when they work together Basically there is a hierarchy in these three number types firstly ComplexNum then RationalNum and DoubleNum comes last So when computing on two different types of number the number with lower hierarchy will change the form to accommodate the higher hierarchy 6 2 1 1 DoubleNum This class inherits from FieldElement It is used to store the decimal number When the system create a DoubleNum instance it pass the decimal number into its field value protected double value When the system operates on the DoubleNum object it actually calculates the value 6 2 1 2 Rational Number The rational number should be in the form of a b which a and b are integers So in rational number there are two variables declared in
73. near Algebra System CO U 3 U 8 U U U 4 U P finally C U U U P U U U P U U 2 4 4 Blockwise inversion Frobenius Lemma This algorithm is used to solve matrix inversion Lemma Let matrix A be divided into blocks A 4 Ay With the matrix All square and non singular and the matrix A Ay is non singular Then X A AA AA 4 4 A A A A The complexity of this algorithm is about O n This algorithm works with some pre conditions which is that the matrix should be either upper triangular matrix or symmetric positive definite matrix So it not work on every non singular matrix However for a arbitrary real non singular matrix A the product of its transpose and itself A A is symmetric positive definite and is symmetric positive definite The problem of calculating the inverse of A becomes calculating the inverse of The calculating the inverse of A A can use this algorithm 26 Linear Algebra System 2 4 5 Artificial Intelligence Artificial Intelligence is referred to the intelligence performed in an artificial man made non natural manufactured entity Generally speaking AI systems are built around automated inference engines By judging certain conditions if the system infers certain consequences then There are two types of AI applications according to conseque
74. nt objects addition result into the new vector Step 6 The operate method returns the new vector which is the result of adding two vectors All other Operators work in a similar way There are two difference operator interface One is DyadicOperator interface which supports application of arbitrary dyadic two argument functions to the elements of two Matrix or Vector objects via the Matrix or Vector s method The other one is the MonadicOperator interface which supports application of arbitrary monadic one argument functions to the elements of a Matrix or Vector via the Matrix or Vector s apply methods The AddOperator SubtractOperator MultiplyOperator and DividOperator implement the Dyadic Operator interface and AbsOperator implements the MonadicOperator 6 2 3 Matrix The Matrix class uses double FieldElement type array to store entries Some of matrix functions also use the operator classes The matrix functions can be divided into three levels The high level functions cannot work until the lower level functions are work properly and the algorithm become more complicated as the level getting further 6 2 3 1 First Level The main functions in the first level are addition subtraction transpose the functions of checking if the matrix in lower triangle or upper triangle forms getting rows or columns and swapping rows or columns The addition and subtraction in Matrix are quite similar to those in Vector The only difference
75. o work on more types of numbers Fox example we can create a class to store the root numbers Adding More number arithmetic We can add more arithmetic functions for each type of number especially the complex number 8 2 2 Linear Algebra Functions Adding more linear algebra functions such as calculating the Eigenvalues and Eigenvectors 78 Linear Algebra System 8 2 3 User Interface Improving the user interface layout Adding command line into the interface to give user more freedom Adding more non mathematical functions like loading external file with matrix of vector recording command history saving the result and so on 8 2 4 Advanced Algorithm Fixing the problem of Blockwise Inverse Developing more algorithms For example LU decomposition which decompose the matrix into upper and lower triangle which can be used to solve the linear equations and matrix inverse The QR decomposition which decompose a matrix into an orthogonal and a triangular matrix The QR decomposition is also the basis for the QR algorithm QR algorithm can be used to calculate the eigenvalues 8 2 5 Artificial Intelligence Developing AI on calculating the determinant of a matrix by using the properties of determinant For example If A has two equal rows of columns then det A 0 Developing AI on other functions Fox example when doing calculation on more then two matrix using the algebraic properties may make the calculation easier
76. ome matrix operations on it Moreover these softwares normally take hundreds of megabits from hard disk to install and a while to start up In addition the most of the existing systems has the problem of compatibility For example the Matlab running in the Windows XP is different from the version running in the Mac OS Considering all above it is very necessary to narrow down scope of mathematics to create a purely Linear Algebra System with the following primary objectives and secondary objectives Primary Objectives Capable of process different types of number such as decimal number rational number or complex number Capable of doing some general linear algebra arithmetic which is actually about vector and matrix operations Capable of implementing some advanced math algorithms with low complexity to do matrix calculations Secondary Objectives Artificial Intelligence Friendly user interface Robust system with error handling functions Independent code structure working on different fields which can make the system easy to improve and develop later Linear Algebra System 2 Literature Review 2 1 Introduction Before getting further to the system designing and coding there are many linear algebra theories I should understand and apply to the project This literature review is going to prove what knowledge and ideas have been established on this project Concerning with the aim of my project
77. ommon editors without running Maple system As a successful and well known mathematics system in industry and academia there are some features that may fit to this project and also some may be not necessary but need to pay attention to improve or change e User interface as mentioned before Maple use work sheet based interface which is flexible to invoke functions and modify input However for beginners they may find the 27 Linear Algebra System language and interface daunting 8 This need to pay attention to avoid in the feature work since this project should have a user friendly interface e Syntax and structure for advanced user Maple provides them a powerful platform to create own functions However it is not easy to use without being familiar and doing some exercise is necessary Because of the scale of my project only focusing on Linear Algebra the simplicity of using the system should be enhanced e Error message Maple is not forgiving of error but subsequent message is not very helpful The flexibility and usability of error message should be considered in my project e Number input Maple allows many different of number type input and they can also work together in the system This feature should be highly considered 2 5 2 Matlab Matlab is another mathematical system with interactive environment with hundreds of built in functions for mathematical computations graphics and external interface It also provides
78. on multiplication Fields 47 Linear Algebra System There are two kinds of field types in this system vector and matrix They are using FieldElement as entries In matrix the attributes numOfRow and numOfColumn refer to the current row or column index They will be used in the afterward functions Each method corresponds to one function in Functional Requirement in the last chapter The methods straOriginal and CopperWinograd will call the responding method in the advanced object det is to calculate the determinant of a matrix eig is to calculate the eigenvalue of a matrix gaussjord is to change the matrix into row echelon form and gausselim is to change the matrix into reduced row echelon form isLowerTriangular and isUpperTriangular are used to check the matrix form in order to apply AI to calculate the determinant This will be discussed in the AI design 48 Linear Algebra System These operators are used to do some general calculations defined in FieldElement The MonadicOperator is used to implement arbitrary monadic one argument functions to the Fieldelement The DyadicOperator is about doing arbitrary dyadic two argument functions 49 Linear Algebra System These classes are using Strassen Algorithm Coppersmith Winograd Algorithms and Block wise as theory to calculate the multiplication and inverse of matrices They also have the
79. ose the type of number you want to create from the Entries Data Type combo box Click Create button Input the number in the entries in the middle of the application window shown right after clicking the Create button The system only accept decimal number for entries After finishing the input click the Confirm button The system will create this Matrix Please make sure every entry has input number Case 3 Implement Calculation on a VectorA B 1 2 3 4 Choose Vector A B the tabbed panel Make sure the Vector A B has been created If not go to the case to create it Choose the function from the function combo box in the bottom left of application window If the function needs to work with a scalar then input the scalar in the scalar text area this text area only accept the decimal number If the function needs to work with another vector or matrix choose the vector name or matrix name from the combo box on the right of Compute With label Before doing that please make if the vector or matrix chosen is not empty Click Get Result button then the result panel will show the result Case 4 Implement Calculation on a Matrix A B 1 2 3 4 Choose Matrix from the tabbed panel Make sure the Matrix A B has been created If not go to the case 1 to create it Choose the function from the function combo box in the bottom left of application window If the
80. ound and executed unless it s in the current directory It is not convenient for the user because the user have to copy the file to the current directory Especially for beginners without being aware of this they will think they did not install the system appropriately or there is something wrong with the configuration 3 Requirements Analysis and Specification 3 1 Introduction In the literature review part literature evidence about the project is provided However they are still theoretical In this part it is the time to analyse these theories to find out what are applicable in the project In addition it is necessary to re consider the required project objectives mentioned in the first part Introduction and discuss them in details However it will not be concerned about how to implement these requirements in this chapter which will be detailed in the system Design part 3 2 Use Cases Use cases is an important part to get a better understanding on the requirement of the system It provides the guideline of analysing literature review and the functional requirement in the next chapter 3 2 1 Scope The scope of the use cases is the all fundamental linear algebra arithmetic It can be divided into two streams vector operations and matrix operations 29 Linear Algebra System 3 2 2 Vector Use Cases Use case 1 Vectors Addition Task Adding two vectors Primary Actor Users Preconditions Users choose the
81. outputs the Transpose of this matrix Rationale It is required from the objective of the project 42 Linear Algebra System 4 2 3 Other functions Index 26 Name Error Message Summary When user input is wrong or make some unexpected operations the system pop up a error message to tell user how to fix errors Rationale It will make the user interface more friendly 4 3 Non Functional Requirements Non Functional Requirements refer to how well the system functions are delivered which include timing constraints constraints on the development process and standards 11 Index 27 Name Reliability Summary The reliability is about how reliably the system work For this project it focuses on the accuracy of doing calculation It is not tolerable to fail getting the right result of calculation Rationale This is what the system must achieve No matter what functions the system provide or how fast the system run if the system can not work probably or fail in a high rate the system is worthless Index 28 Name Compatibility Summary The system should work on recent computers and usual operation system Rationale There is no need to writhe different version for this scale of system for running on different OS So the compatibility must be high in this system Index 29 Name Maintainability Summary The system should allow for new developers to carry out maintain
82. ple the system returns error message when adding different dimension of matrices If it works on DoubleNum then it should also work on other two types because checkDimension actually do not process on these numbers The numbers data and functions using in this system are quite closely connect to each other It has a quite strong function hierarchy like the three levels of matrix functions mentioned in the Implementation The pre conditions of the functions in the higher level working probably is that the functions in the lower class must work well Since there are 20 classes and tens of methods in this project it is quite hard to test all classes and methods So the testing shown in here will focus on testing the methods and function in high hierarchy 7 2 Function Testing In this part the system will be tested by input certain numbers and check if the output is what expected The input will be both in right or wrong form and different types of number 7 2 1 Vector Functions Vector Addition Scalar Vector Scalar Expected Result Actual Result Status 3 2 11 5 8 7 16 8 7 16 Pass Null 5 Error Message Error Message Pass 1 2 2 3 4 7 2 3 2 4 3 21 7 3 2 4 3 21 7 Pass 2 61 3 31 9 71 3 5 61 6 31 5 61 6 31 Pass 12 71 12 71 Vector Addition Vector Vector A Vector B Expected Result Actual Result Status 1 2 6 2 4 1 3 67 3 6 7 Pass 3 1 7 2 4 Error Mes
83. ply m2 getCol j return resultMatrix The original Strassen Algorithm for matrix multiplication param ml param m2 return ml multiplied by m2 throws InvalidOperationException ay public static Matrix strassenOriginal Matrix ml Matrix m2 checkDimensions ml m2 if checkSize ml m2 int endIndex ml getRows int splitIndex endIndex 2 System out println m1 Matrix all ml getMatrix 1 splitIndex 1 splitIndex Matrix al2 ml getMatrix 1 splitIndex splitIndex 1 endIndex Matrix a21 ml getMatrix splitIndex 1 endIndex 1 splitIndex Matrix a22 ml getMatrix splitIndex 1 endIndex splitIndex 1 endIndex 92 endIndex splitIndex endIndex Matrix bll m2 getMatrix 1 splitIndex 1 Matrix bl2 m2 getMatrix l splitIndex Matrix b21 m2 getMatrix splitIndex 1 endIndex Matrix b22 m2 getMatrix splitIndex 1 endIndex Linear Algebra System splitIndex splitIndex 1 println all toString strassenOriginal all add a22 strassenOriginal a2l add a22 strassenOriginal all strassenOriginal a22 strassenOriginal all add al2 1 splitIndex 1 bll add b22 511 bl2 subtract b22 b21 subtract b11 522 System out Matrix pl Matrix p2 Matrix p3 Matrix p4 Matrix pd Matrix p6 Matrix p7 System out strass
84. ponent in the k 2 position where the second part of the rational number is m set sets the rational number just read in the matrix Then it calls currentCol to point to the next entry of the matrix 6 5 Error and Exception Handling The structure of Error and Exception Handling is quite simple Define some new exception class Create an exception instance with an exception message in the functions which may cause errors and throw this error Catch the exception instance in the methods which call the functions with exception instance and get the message from the instance Pop up an error message Example 65 Linear Algebra System The method in Matrix Class public FieldElement get int rowIndex int 1 throws InvalidOperationException throw new InvalidOperationException Tried row index rowIndex Only row indices from 1 to this numOfRows valid Please input the matrix with right dimension The method in LAS class private void matrixoperations catch InvalidOperationException e ErrorMess createErr e getMessage In the matrixoperations method it will call the methods to do calculations on matrix and these method will call get method from Matrix Class If the get method fails to get the matrix entry it throw InvalidOperationException with the test message Then in the matrixopertions will catch this exception and call
85. pute button Users get the result Use case 12 Matrix Determinant Task Primary Actor Calculate the determinant of a matrix Users 32 Preconditions Process Result Linear Algebra System Users choose the determinant function from the system Users input one matrix Users press compute button Users get the result Use case 13 Gauss Jordan Elimination Task Primary Actor Preconditions Process Result Use case 14 Matrix Rank Task Primary Actor Preconditions Process Result Calculate the Reduced row echelon form of a matrix Users Users choose the Gauss Jordan Elimination function from the system Users input one matrix Users press compute button Users get the result Calculate the Rank of a matrix Users Users choose the Rank function from the system Users input one matrix Users press compute button Users get the result Use case 15 Matrix Transpose Task Primary Actor Preconditions Process Result Use case 16 Matrix Inverse Task Primary Actor Preconditions Process Result Calculate the Transpose of a matrix Users Users choose the Transpose function from the system Users input one matrix Users press compute button Users get the result Calculate the Inverse of a matrix Users Users choose the Inverse function from the system Users input one matrix Users press compute button Users get the result 33
86. r column to calculate the determinant 3 3 4 User Interface The user interface in this project is not the key objective It does not need a fully functional and professional interface The most important features are simplicity and user friendliness which can make the users start using quickly and even without reading user manual Considering the scale of the project the errors or mistakes made by the users are limited So the system should provide a helpful error message function which tells users how to fix the error or mistake 35 Linear Algebra System 3 4 Number Structure Input and Output 3 4 1 Number Structure Either vectors or matrices need numbers for their entries So the system should be capable of reading user input in different forms In this stage it is defined that the number entries should be in three different forms decimal number rational number and complex number These three different number types should independent exist in the system However in maths theory these three forms can be actually transformed from each one So although they need to be entity independent they also need to be function dependent which means it works that doing a computation between two different types of number 3 4 2 Data Input and Output Before using functions in the system to calculate vectors or matrix the users must input data in the system to create a vector or matrix These input is actually refer to two aspect entries
87. re n 1 zeros in a row the complexity of calculating the 50 Linear Algebra System determinant is still big So the system will only check if there is a row or column of Os If there is the system will return 0 Or the system uses Gaussian elimination to reduce the matrix into upper triangular form then multiply the main diagonal to get the determinant The operation of doing Gaussian elimination is about n 3 which the complexity is O n 5 5 User Interface Design Since the simplicity and user familiarity are the main goals of the interface it should be designed in a user friendly way which means the users can easily find the function they want to use and be clearly aware of what they doing This is the draft user interface Menu Bar Vector A Vector B Matrix A Matrix B Result Vector or Matrix Creating Tool Bar Vector or Matrix size input NumberType Selcetion combo box Create Button Vector or Matrix Entries Function Tool Bar Function Selection combo box Scalar input vector or matrix selection combo box implement button There are five components in this interface design The first one is the menu bar which has menu items in it Since the user interface is the secondary objective in this project there will only be some simple functions like clear the result panel quit the system some system information functions The second part is the tabbed panel which has Vector A B Matrix A B
88. ree elementary operations Interchange two rows Replace a row with a nonzero multiple of itself Replace a row with the sum of itself and a multiple of another row 2 3 1 2 Matrices and Linear Equations In this session I will introduce the way of using matrices to describe and solve linear equations 13 Linear Algebra System For the system of linear equation X 3 3x 7 2 2x3 6 9 4x 6x3 1 There are two kinds of matrix to represent this One is the matrix of coefficients formed by the coefficients of variables The other one is the augmented matrix consisting coefficients and constant terms together 1 1 1 L 1 1 3 3 7 2 3726 9 4 6 9461 matrix of coefficients augmented matrix Reduced echelon form When solving a system of linear equations the augmented matrix is often used In order to get the result we need to transform the augmented matrix into reduced echelon form A matrix is in reduced echelon form if 1 Any rows consisting entirely of zeros are grouped at the bottom of the matrix 2 The first nonzero element of each other row is 1 This element is called a leading 1 3 The leading 1 of each row after the first is positioned to the right of the leading 1 of the previous row 4 All other elements in a column that contains a leading are zero The follower matrices are all in reduced echelon form 1000 1000 01 8 0 0 1 0 0 0 0 0 I 00 1 0 00 0 0 0001 The following
89. rices Compute another seven matrices by using additions subtractions and multiplications on sub matrices Calculate the n 2 n 2 sub matrices of C from addition the previous seven matrices Lemma if Cii 1 Cs 2 5 2 2 A 1 gt Aoi As Bi Bi m Bj B Then Aii A22 B B22 A2 24 Linear Algebra System A i Bi 2 B22 M Ms A21 Ai Bii 2 M A15 Finally Ciia M M M M7 M M C21 M C22 M M M M In Strassen algorithms the time complexity is only n which is n 9 6 reduced from the standard matrix multiplication with time complexity of n 2 4 3 Coppersmith Winograd algorithm In the mathematical discipline of linear algebra the Coppersmith Winograd algorithm is the fastest currently known algorithm for square matrix multiplication It can multiply two nxn matrices in O n and the O n time Strassen Algorithm d Lemma if 2 ja A Ay A S A Ay S S 4 F A B S 4 P Ba 5 S BST Then after that P S 7 B 5 T B5 T R S T Bj T T B4 T 25 time see Big O notation 7 This is an improvement over the trivial O n time algorithm Li
90. s Assume that the sizes of the matrices are such that the operations can be performed Properties of Matrix Addition and Scalar Multiplication 2 1 A B B A Commutative property of addition 2 A B C A B C Associative property of addition 3 where O is the appropriate zero matrix 4 c A B cA cB Distributive property of addition 5 at b C aC bC Distributive property of addition 6 ab C a bC Properties of Matrix Multiplication 1 A BC AB C Associative property of multiplication 2 A B C AB AC Distributive property of multiplication 3 A B C AC BC Distributive property of multiplication 4 Al 1 A A where I is the appropriate identity matrix 5 c AB cA B A cB Note 2 3 3 1 The transpose trace inverse of matrices Transpose Definition The transpose of a matrix A denoted A is the matrix whose columns are the rows of the given matrix Example 1 2 1 3 4 A 3 6 2 6 9 4 9 Trace Definition Let A be a square matrix The trace of A denoted tr A is the sum of the diagonal elements of A Thus if A is an n n matrix tr A 22 Example 1 3 A 2 6 tr A 1 6 2 9 35 N O Properties of Transpose and Trace Linear Algebra System Let A and B be matrices and c be a scalar Assume that the sizes of the matrices are such that the operations can be performed 2 1 A B A 2 cA 3
91. sage Error Message Pass 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 14 7 2 11 6 11 14 7 12 11 6 11 14 Pass 12 4 1 2 1 4 2 3 3 2 9 4 14 3 3 2 9 4 14 3 Pass 1 2 1 4 2 3 124 3 2 9 4 14 3 3 2 9 4 14 3 Pass 4 7 2 2 61 343i 9 71 646i 10 31 6 6i 10 31 Pass 11 7i 11 7i 67 Linear Algebra System 2 61 3 31 9 71 4 7 2 6 61 10 31 6 61 10 31 Pass 11 7i 11 71 1 2 1 4 2 3 2 i 4 3 2 1 9 4 3 2 1 9 4 1 14 3 1 14 3 1 14i 2 i 4 1 2 1 4 2 3 3 21 9 4 3 271 9 4 Pass 14 341 14 3 1 Vector Subtraction Scalar Vector Scalar Expected Result Actual Result Status 3 2 11 5 2 3 6 2 3 6 Pass Null 3 Error Message Error Message Pass 5 2 8 3 20 7 2 1 2 2 3 6 7 1 2 2 3 6 7 Pass 246134319971 3 1 61 0 31 6 71 1 61 0 31 6 71 Pass Vector Subtraction Vector Vector A Vector B Expected Result Actual Result Status 1 2 6 2 4 1 1 2 5 1 2 5 Pass 3 1 7 2 4 Error Message Error Message Pass 4 7 2 Null Error Message Error Message Pass 1 3 3 2 4 7 1 4 1 3 3 14 1 12 7 6 5 14 1 12 7 6 5 14 Pass 12 4 1 2 1 4 2 3 1 2 7 4 10 3 1 2 7 4 10 3 Pass 1 2 1 4 2 3 124 1 2 7 4 10 3 1 2 7 4 10 3 Pass 4
92. so these two testing could combining together In a addition all function testing actually used user interface to implement the function So this interface test will just ignore testing the mathematical functions in the interface Interface Testing Action Expected Result Actual Result Status Input the size of a The test area shows The test area shows Pass vector or matrix in the the input the input text area Choose the data type The combo box shows The combo box shows Pass from the combo box the selected number the selected number type type Click on create It create some text area It create some text area Pass button entries and labels in and labels in the the middle part of the middle part of the application window application window according to the size according to the size and number type input and number type input Input the number in It shows input It shows input Pass the entries Click confirm button The vector or matrix The vector or matrix Pass created is shown in the created is shown in the result panel result panel Select function from The combo box shows The combo box shows Pass the function the selected function the selected function combo box at the name name bottom Input number in scalar It show input It shows input Pass area Select the vector or It shows the selected It shows the selected Pass matrix to compute the vector or
93. solution situations will be carried on in the following sections Linear Algebra System 2 3 2 Matrix Operations 2 3 2 1 Addition Scalar Multiplication and Multiplication of Matrices Addition of Matrices Definition Matrices addition can only happen between two matrices with same dimension The sum of matrix A B is obtains by adding the elements in the same location The result matrix of A B also has the same size as of A and B Example 1 3 4 3 6 4 A B f 2 7 4 N 143 346 444 4 9 8 A B pe 2 4 16 6 Scalar Multiplication Definition If A is a matrix C is a scalar then B cA is obtained by multiplying each elements in A by c The B will be the same size as A 1 3 4 A c 3 f 2 j 1x3 3x3 4x3 3 9 12 B cA be 2x3 6 Multiplication of Matrices Example Definition The matrix A and B can be multiplied only if the number of columns in A is same as the number of rows in B The element in the location of i j in the product of AB is obtained from the sum of multiplying product of corresponding elements of row i in A and column in B IfA a a B then by Example 2 6 10 2 4 3 5 1 12 20 4 1 3 5 1 So if A is an m r matrix is an r n matrix then will be an m n matrix 16 Linear Algebra System 2 3 3 Algebraic Properties of Matrix Operations Theorem Let A B and C be matrices and a b and c be scalar
94. tion Class public static Matrix simple Matrix ml Matrix m2 throws InvalidOperationException checkDimensions ml m2 int resultRows ml getRows int resultCols m2 getCols Matrix resultMatrix new Matrix resultRows resultCols for int i 1 i lt resultRows irr for int j 1 j lt resultCols jtt resultMatrix set i j ml getRow i multiply m2 getCol j return resultMatrix The checkDimensions is to check the dimensions of two matrix to see if they can be multiplied The ml getRow i and m2 getCol j in the second for loop return the ith row of matrix m1 and the jth column of matrix m2 as two vectors So instead of getting each entry of two vectors and multiply them the system uses vector multiplication function which is resulting dot product in fact And this dot product is just the entry in the new matrix There are the other two method in this MatrixMultiplicaion class But those two will be discussed in the Advanced Algorithms session Gaussian Elimination gausselim This function is to change the matrix into the row echelon form by using row operations It uses the 57 Linear Algebra System getRow and swapRows function from the first level and operations in Vector class There are two steps in this method 1 Find the non zero diagonal entry Firstly it check the entry in the first diagonal If the diagonal entry in the current row is
95. tiplications to calculate the final result In addition according to Strassen Algorithm explained in the literature review there have to be some temporary matrices to store the submatrices and their operations So the first step of applying this method is to check if two matrices dimension are multipliable and meet the pre condition of using this algorithm Then it goes to division step The original two matrices will be divided into four equal dimension submatrices As it is required we should use the recursive division in here So the method calls itself in the content of the method int endIndex ml getRows int splitIndex endIndex 2 Matrix all ml getMatrix 1 splitIndex 1 splitIndex Matrix 12 ml getMatrix 1 splitIndex splitIndex 1 endIndex Matrix a21 ml getMatrix splitIndex 1 endIndex 1 splitIndex Matrix a22 ml getMatrix splitIndex 1 endIndex splitIndex 1 endIndex Matrix bll m2 getMatrix 1 splitIndex 1 splitIndex 61 Linear Algebra System Matrix 612 m2 getMatrix 1 splitIndex splitIndex 1 endIndex Matrix b21 Matrix b22 m2 getMatrix splitIndex 1 endIndex 1 splitIndex m2 getMatrix splitIndex 1 endIndex splitIndex 1 endIndex The next step is to calculate from M to M details can be seen in the Literature Review Strassen Algorithm section This is where the method calls itself So when submatrices doing multiplication
96. to crush 2 Although the system can skip the non TextField Component it also need to be aware of which 6 4 Linear Algebra System what part of number it is reading when processing rational and complex number which index should put it in the vector or matrix The approach to solve first problem is to use a if statement to check the type of the component If the type is right the syterm read or ignore it if compType equals javax swing JTextField ntry JTextField jc getComponent k getText The way to solve the second problem is analysing the number of component firstly then when the system read the first part of the rational or complex number force the system go to the second part entry In order to put the number into the right index the system employ index variable if compType equals jJavax swing JTextField String numeratorEntry JTextField jc getComponent k getText k k 2 String dominatorEntry JTextField jc getComponent k getText BigInteger numeratortmp null BigInteger dominatortmp null try numeratortmp new BigInteger numeratorEntry dominatortmp new BigInteger dominatorEntry 1 1 currentCol new RationalNum numeratortmp dominatortmp currentCol t When the condition of if is true the system reads this first part of the rational number Then it makes k k 2 to reading the com
97. tor B Matrix A and Matrix B and Result Vector A Vector B Matrix A and Matrix B panel are used to create vectors and matrices The Result panel is for showing the calculation result File Help Vector A VectorB Matrix A Matrix Result Norm v Scaler Compute With Vector A w Get Result Length Entries Data Digits Create Vector Confirm User cases Case 1 Creating a Vector 1 Choose the vector panel from Vector A and Vector B 2 Input the length of the vector you want to create in the text area on the right of Length The system only accept the positive integer 3 Choose the type of number you want to create from the Entries Data Type combo box 4 Click Create button 5 Input the number in the entries in the middle of the application window shown right after clicking the Create button The system only accept decimal number for entries 6 After finishing the input click the Confirm button The system will create this Vector Please make sure every entry has input number Then the result panel will show the vector just been created 97 Linear Algebra System Case 2 Creating a Matrix 1 2 Choose Matrix panel from Matrix A and Matrix Input the length of row and column you want to create in the row and column text area The system only accept the positive integer Cho
98. u 4 u u 0 5 v 6 7 8 c dju cu du c du cd u 2 3 5 2 Dot Product Cross Product Norm Angle and Distance Dot Prodect Definition u uj Un and v V Vn are two vectors The dot product of u and v v 21 Linear Algebra System uj Vit Un Vg Example 1 2 4 and v 3 0 2 uev 1x3 2x0 4x2 11 Cross Product There is another way to combine two vectors apart from dot product b a b a b Definition a a b b axb a b Being aware of this this result is a vector bi a b a b More important the cross product can only apply to 3 vectors Exmaple 1 4 4 1 2 6 8 141 b 6 2 4 1 1 7 2 1 1x6 4x4 10 Norm Definition the norm of u uy up is defined as u Definition the unit vector for a nonzero vector v is Example 2 4 1 la N2 4 2 J21 Angle Definition The angle between two vector and v is defined as cosO u v u v OS 0 SIT Theorem if the product of nonzero vector is 0 then the vector u and v are orthogonal Example u 1 0 0 and v 1 0 1 u v lt l ul 1 v V2 uev 1 0 v2 The angle between and vis 45 Distance Definition x x1 x and y Y yn are two points The distance between x and y d x y Ix y 2 3 5
99. vertible see Literature Review Blockwise Algorithm This limits the algorithm So in order to apply this algorithm to an invertible arbitrary real matrix it requires another lemma which is for A which is invertible y and A A is symmetric and positive definite which can use this algorithm Moreover in Blockwise algorithm there are two 62 Linear Algebra System matrices which need to calculate the inverse So the system could call this method recursively until reach 1 1 matrix So the first step is to check if the matrix is invertible and calculate the Then the method decomposes the matrix A A into four submatrices A11 A12 A21 An After that it calculates the delta and four entries of A A by using the Blockwise lemma and reconstructing the matrix Finally by multiplying the inverse of 47 and A the final result is found Details in Appendix A MatrixInvers clasee 6 3 4 det det is the only method concerning with AI in this project The implementation of the AI in calculating the determinant is exactly followed AI design in 5 4 It invokes isUpperTriangle and isLowerTriangle first to implement the first method of AI If the matrix is the system calculates the product of the diagonal entries If the matrix is not it runs two for loops to check if there is a row or column of Os by calling isZeroRow and isZeroCol If there is return 0 Or it change the matrix
100. y al2 multiply deltaInverse multiply new DoubleNum 1 Matrix c21 deltalnverse multiply a2l multiply allInverse multiply new DoubleNum 1 Matrix c22 deltalnverse 89 Field Linear Algebra System FieldElement cllEntries cll getEntries FieldElement cl2Entries cl2 getEntries FieldElement c2lEntries c2l getEntries FieldElement c22Entries c22 getEntries FieldElement cEntries new Element m getRows m getCols for int i 0 i lt cll getRows i for int j 0 j lt cll getCols j cEntries i j cllEntries i j for int i 0 i lt cl2 getRows i for int j 0 j lt cl2 getCols j cEntries i j splitIndex cl2Entries i j for int i 0 i lt c21 getRows i for int j 0 j lt c21 getCols j cEntries i splitIndex j c21Entries i jl for int i 0 i lt c22 getRows i for int j 0 j lt c22 getCols j cEntries i splitIndex j splitIndex c22bEntries i jl Matrix mInverse new Matrix cEntries System out printin mInverse toString System out printin mTranspose toString j mInverse mInverse multiply mTranspose return mInverse 90 Linear Algebra System MatrixMultiplication Class package Backend This i

Wang-K-dissertation - Department of Computer Science

Contents

Download Pdf Manuals

Related Search

Related Contents