LAME: Linear Algebra Made EasyDavid GolubCarmine ElvezioAriel DeitcherMuhammad Ali AkbarDecember 20, 20101 Project ProposalWe propose to develop a language with built-in support for linear algebra andmatrix operations. The language will provide functionality similar to MATLABfrom The MathWorks, Inc. However, the syntax will be similar to C, C++, orJava.Our language will provide four primitive data types, scalar, matrix, string,and Boolean. These data types will do as their names suggest. A scalar will holda double-precision floating point number. A matrix will store a two-dimensionalarray of double-precision floating point values. Matrices will be declared usingcommas to separate columns and semicolons to separate rows. For example, thecodematrix A = {1, 2, 3;4, 5, 6;7, 8, 9};will correspond to the matrixA =1 2 33 5 67 8 9in the standard notation from linear algebra. Individual elements of a matrixvariable will be able to be access and modified using the syntax A[i, j] forthe element in the ith row and the jth column. Keywords will be provided toobtain the dimensions of a matrix.Operators will be provided for addition, subtraction, multiplication, division,and exponentiation. The operators will be interpreted appropriately for various1combinations of operand types, as long as they are mathematically meaningful.Combinations of operand types that are not mathematically meaningful, suchas division of two matrices, will yield a compiler error. When matrix operationsare performed, a check will be done at runtime to ensure that the dimensionsare compatible. If the check fails, a runtime error will be thrown.The language will follow the imperative paradigm and will provide constructsfor variable assignment, decisions, loops, and basic I/O. Programs will be trans-lated to an intermediate code and then to C++ code using a custom library.The C++ code can then be compiled to native code.2 TutorialThis is a beginner’s tutorial to LAME. LAME is a C-like programming languagefor linear algebra. It allows a mathematician to implement algorithms involvingmatrix operations with a very short learning curve.This tutorial is divided in to three parts. First, we describe the steps involvedin compiling and running a simple “Hello, World!” program. Then, we describehow to perform basic matrix operations. Finally, we explain the construction ofa program that implements the algorithm to solve a system of linear equations.2.1 Getting StartedWe start by writing a very basic program that prints “Hello, World!”2.1.1 “Hello, World!” ProgramType the following program in a file names hello.lam.print "Hello, World!";The print keyword takes a string as an argument and prints that string to theoutput console. Each statement in LAME ends with a semicolon.2.1.2 Compiling and Running the ProgramYou should have a C++ compiler on your machine. The lame.exe executable,the compiler.bat script, the lame.h and matrix.h header files should bepresent in the working directory for the compilation.Windows: First, we give instructions for a Windows machine with VisualC++. First set up the environment by running vcvars32.bat file from VisualStudio’s common folder in the installation path. Alternatively, you can usethe Visual Studio Command Prompt which automatically sets the environmentvariables for the compiler.Now run the following commands to compile and run the program:2> lame.exe < hello.lam > program.cpp> cl.exe /EHsc program.cpp> program.exeAlternatively, you can use the provided batch script by using following com-mand:> compiler.bat hello.lam> program.exeLinux: Run the following commands to compile and run the program:# ./lame < hello.lam > program.cpp# g++ program.cpp -o program# ./programIf running the program prints “Hello, World!” on a separate line on the screen,and you are ready to go to next part of the tutorial.2.2 Basic Matrix OperationsLet’s write a program that declares a matrix with initial values and prints thematrix:matrix A = { 1, 2; 3, 4 };print "A = \n" + A;Let’s declare another matrix B and add it to the matrix A:matrix B = { 4, 3; 2, 1 };matrix C = A + B;print "A + B = \n" + C;Subtraction and multiplication of matrices are done in similar manner. Let’smultiply the matrix by a scalar value:matrix D = 2 * A;print "2 * A = \n" + D;Let’s change the value of an element in A and print the value of an element inB:A[0, 1] = 20;print "B[1, 1] = " + B[1, 1];3The following if statement prints “True” and the while loop prints all elementsof matrix A:if(A[0, 0] == 1) {print "True";} else {print "False";}scalar i = 0;scalar j = 0;while(i < 2) {while(j < 2) {print A[i, j] + "\n";j = j + 1;}i = i + 1;}2.3 Case Study: Solving Linear System of EquationsLet us implement an algorithm using LAME to solve a system of simultaneouslinear equations. The equations are3x1+ x2= 3and9x1+ 4x2= 6.We use the following algorithm to solve this problem:A =3 19 4B =36X =x1x2= A−1BA−1=1|A|Adj(A) =1A0,0A1,1− A0,1A1,0A1,1−A0,1−A1,0A0,0This algorithm has been implemented in LAME as follows:matrix A = { 3, 1; 9, 4 };matrix B = { 3; 6 };matrix X;print "\nSolving system of simultaneous linear equations:\n";4print A[0,0] + " x1 + " + A[0,1] + " x2 = " + B[0] + "\n";print A[1,0] + " x1 + " + A[1,1] + " x2 = " + B[1] + "\n";print "\nA = \n" + A + "\n";print "\nB = \n" + B + "\n";scalar det_of_A = A[0,0]*A[1,1] - A[0,1]*A[1,0];print "\nDeterminant(A) = " + det_of_A + "\n";if(det_of_A != 0) {matrix inv_of_A;inv_of_A [0,0] = A[1,1];inv_of_A [0,1] = -1*A[0,1];inv_of_A [1,0] = -1*A[1,0];inv_of_A [1,1] = A[0,0];inv_of_A = inv_of_A / det_of_A;X = inv_of_A * B;print "\nInverse(A) = \n" + inv_of_A + "\n";print "X = Inverse(A) * B = \n" + X + "\n";print "Solution:\n";print "x1 = " + X[0] + "\n";print "x2 = " + X[1] + "\n";} else {print "A is singular and its inverse doesn’t exist.\n";}The program prints out the following output:Solving system of simultaneous linear equations:3 x1 + 1 x2 = 39 x1 + 4 x2 = 6A =3 19 4B =36Determinant(A) = 3Inverse(A) =1.33333 -0.333333-3 1X = Inverse(A) * B =2-35Solution:x1 = 2x2 = -33 Language Reference Manual3.1 Definition of a ProgramA program is a sequence of variable declarations and statements.3.2 Variable Declarations3.2.1 Data TypesThe following data types represent the complete listing of primitives availableto a programmer of LAME.• Scalar: This is the equivalent of a double precision floating point numberin most languages. The value is
View Full Document
Unlocking...