Introduction (Program Functionality Description) This week you are going to write a…

Introduction (Program Functionality Description) This week you are going to write a single recursive function m-file to perform Gauss Elimination with partial pivoting on a system of linear algebraic equations. Your function will be passed (through the header) a square [A] matrix and a matching [b] column vector. Your function will return the [x] solution vector to the matrix equations [A][x] = [b].

Deliverables You will upload to Canvas a single file, titled LastNameFirstInit_Lab7.m, containing the results of Task #1, below.

Introduction to Recursion Recursion is a programming concept in which a function, when asked to perform process A on system Q, rather than performing process A on system Q, instead

1. performs process B (a subset of process A) on system Q, resulting in a system that looks like Q, but may be “smaller” or “simpler” is some manner (let’s call this system R),
2. launches a new instance of itself, asking the new instance to perform process A on the new system R,
3. waits,
4. receives from the new instance the results of process A performed on system R,
5. performs process C (a different subset of process A), which uses the results it received from the new instance, along with it’s own remains of system Q, n what it receives from the new instance. The result of this extended process must be equivalent to performing process A on the original system Q (which is what it was asked to do). There are a couple important facets missing from the above description – they will be dealt with later.

Terminology When a function launches a new instance of itself, it is often referred to as spawning. Thus, the spawned instance is called the child, and the spawner is called the parent. An instance can be both a child and a parent at the same time. When a parent sends information to its child, I refer to it as “passing down” the information. When a child sends information to its parent, I refer to it as “passing back” or “passing up” the information.

Multiple instances of a single program? It may seem outrageous to have multiple instances of a single program running, but consider the following. Imagine your currently-running function .m-file needs to execute the line of code: y = cos(0.75) When MATLAB gets to this line of code, it knows to go the hard drive, find the file named cos.m, launch a processor-based copy of the file, and send to it the value 0.75. While the new program runs, your function is still running, waiting patiently for the results to be returned to it. Now, imagine that your currently running function (KahunaB_Lab7.m) needs to execute the line of code: x = KahunaB_Lab7(A,b) MATLAB will go to the hard drive, find the file named KahunaB_Lab7.m, spawn (launch) a new processor-based instance (copy) of the file, and pass to it the values in data structure A and the data structure b. The current instance of the function (the parent) is unaffected – it itself is merely an earlier-spawned, processor-based instance of the actual file on the hard drive. The current instance behaves the same as if it had called the cos built-in function. It waits patiently for the results to be returned. No data structures in the parent instance are affected – remember, the new instance is operating in its own little variable workspace, just as the function cos was when it was running. Keep in mind, it is possible that the “current” instance of KahunaB_Lab7 was actually spawned by a previously running instance of KahunaB_Lab7. It is also possible that the “new” instance of KahunaB_lab6 will spawn yet another instance of KahunaB_Lab7.

Important to grasp recursion concepts There are several concepts to recursive programming that may take some time to get used to, so you may as well start on them now:

1. There can be multiple instances of one function running at the same time. All but the most recently-spawned instance is waiting patiently for its child to return a solution to its question (just as, earlier in the lab session, many of you were waiting impatiently for your “child” classmate to return the factors of the number handed to him/her).
2. The multiple instances exist in a parent-child-grandchild-greatgrandchild, etc. hierarchy.
3. Each instance is aware only of what it was given by its parent and what it gets back from its child. I repeat, each instance has NO KNOWLEDGE of its parent’s variable workspace.
4. Each instance has its own copy of any variables, so changing a variable in one instance has no effect on any other instance’s variables, and
5. The data structure one instance refers to as ‘x’ may be a completely different data structure than what any other instance refers to as ‘x’. This one’s a biggie.

Critical aspects of a recursive function During the in-class exercise, we saw that a recursive function’s behavior is different if it is the terminal (last) instance, vs. if it is a non-terminal instance. However, we must remember that there is only one version of the code. This implies that our function will need to include branching – one block of code that is performed if the instance is the terminal instance, and another block of code that is performed if the instance is non-terminal. This branching further implies another facet of the code. How does an instance know if it is the terminal instance? In total, there are five critical components of any recursive function. They are:

1. Code needed to identify whether or not this is the terminal instance
2. What the code must do if this is the terminal instance
3. If the instance is non-terminal, then
4. what the code must to in order to identify the smaller or simpler system that it will pass to its child,
5. the pawning of the child, and
6. what the non-terminal instance does with the results it got back from its child, in order to complete the solution of the problem it was given by its parent Part 2 and Part 3 will be contained within an if-else statement, i.e. if this instance is terminal do Part 2, else do Part 3. Inherent in part 3)a. What does it do on the way down? is the question, what does a “smaller” system look like. This is a good starting point of the recursive programming process. In the next section you can find code that recursively performs the in-class exercise. It explains the structure and components of a recursive process.

Rough Outline of Function Script Having performed Gauss Elimination with partial pivoting for the HW, you are hopefully familiar with the process. There are four important steps to recursion: • Identify what a “smaller” system looks like I discussed this in the lecture on Gauss Elimination. If you don’t remember, go through the posted example, and see if you can figure it out. • Identify the process to reach the smaller system This was also discussed in lecture. One part that we haven’t discussed yet is the importance of identifying the format of the information passed down to the child instance. It must be in the same format as the information that was passed into the current instance from its parent. • Identify when to stop What is the condition that causes this iteration to not perform row operations? Identify the upward propagation process This is interesting for Gauss Elimination. There are essentially three substeps: • identify what information the current instance gets back from its child, in the reference frame of the current instance (as opposed to what it is in the reference frame of the child) • identify what information the parent of the current instance is expecting to get back from the current instance, again in the reference frame of the current instance • create the latter information, probably using or including the former information

Write the Outline You are not required to write an outline, but it is probably a good idea. If you come to me or the TA’s later with questions or code that imply that you don’t really get the process of what’s going on, we will probably request you to write an RPO. Once you have decided how you are going to handle the concerns above, it is time to write your RPO. Remember that your RPO must include an accurate representation of all loops and branching.

Task #1 Write a recursive function to solve a system of linear algebraic equations using Gauss Elimination with partial pivoting. Your function will be passed a square [A] matrix and a corresponding (same number of rows) [b] column vector. Your function should return to its calling program the answer to the matrix equation [A][x] = [b]. Your function should also perform the minimum amount of work both a) in identifying the system to pass to its child, and b) in processing the answer it receives from its child to identify the answer it must pass back to its parent.

Some Hints for Your Script (LastNameFirstInit_Lab7.m) a) To refer to the portion of matrix A from a13 to a45, the syntax is A(1:4, 3:5) b) To refer to the entire 3rd column of matrix A, use A(:, 3) c) The above syntax can be on the right hand side of an assignment statement to retrieve the values from the matrix, or on the left hand side to store values into the matrix.

Function Output Your program will produce no output to the screen. It must return to its parent the solution to the matrix equation [A][x] = [b].

Code for Finding the Prime Factors of a Number Recursively 1 % We always start with our function header. We are passed 2 % in a single number. 3 function factors = recursive_factorize(prod) 4 5 % I usually start with the terminal instance. According to 6 % the algorithm we used in class, if the function receives a 7 % one (1) through the header, then it is the terminal 8 % instance, and it returns a null matrix. 9 if prod == 1 10 factors = [] 11 12 % Note that the entire rest of this program is in the 13 % ‘else’ portion of this if-else statement. So if prod = 1, 14 % the null array is immediately returned to the parent 15 16 else 15 % The first factor we check for is 2. 16 fac = 2 17 18 % We keep going until we find a factor, so I’m going to 19 % use a while loop. To ensure we get into that while 20 % loop I’m going to use a gateway variable. 21 found = 0; 22 while ~found 23 if mod(prod,fac) == 0 22 % This is what we do if identify a “smaller 23 % system” to pass to our child 24 prod = prod / fac 25 26 % The function is recursive. This instance waits 27 % here for the child to respond. 28 factors = recursive_factorize(prod) 29 30 % This is what we do to convert our child’s 31 % response into the response we will pass back to 32 % our parent. 33 factors = [fac, factors] 34 35 % We need this to quit the while loop and 36 % actually pass the result back to our parent. 37 found = 1; 38 39 % if fac is not a factor of prod, we continue our 40 % search by incrementing fac and repeating the loop. 41 % How we increment fac depends on the value of fac 42 elseif fac = 2 43 fac = 3 44 else 45 fac = fac + 2 46 end %inner else-in 47 end %while 48 end %main else-if 49 end % function

What would the function look like following task #1?

Can you change the code you just made to follow the hints for the function script I gave you while still performing the same

Here is the code I have: function x = ClarkN_Lab7(A, b) % Get matrix dimensions n = size(A, 1);

% Check if this is the terminal instance
if n == 1
    x = b / A; % Solve the single equation
else
    % Perform partial pivoting
    [~, pivot_index] = max(abs(A(:, 1))); 
    A([1, pivot_index], :) = A([pivot_index, 1], :);
    b([1, pivot_index]) = b([pivot_index, 1]);

    % Get the new A_prime and b_prime
    A_prime = A(2:end, 2:end);
    b_prime = b(2:end) - (b(1) * A(2:end, 1) / A(1, 1));

    % Form the smaller system
    A_prime = A_prime - ((A(2:end, 1) * A(1, 2:end)) / A(1, 1));

    % Recursion step: solve for the smaller system
    x_recursive = ClarkN_Lab7(A_prime, b_prime);

    % Calculate the first element of x vector based on the smaller system solution
    x1 = (b(1) - A(1, 2:end) * x_recursive) / A(1, 1);

    % Combine the results to form the final solution vector
    x = [x1; x_recursive];
end

end

Would this code pass the "critical aspects of a recursive function" and the recursion concepts that I gave you earlier?

For the pivoting operation, how to swap the rows in one line of code can be done with code similar to this: A([1,4],:) = A([4,1],:)

Implement that line of code into the function as well.