Frontal solver by Bruce Irons? Am I using the right Algorithm here?

I am writing my Thesis on Direct Methods for sparse Matrizes, especially Frontalsolvers.It took me a while but I finally figured out how the Multifrontalsolver by Duff and Reid works.

But my Professor wants me to have the "original" Frontalsolver by Bruce Irons analysed aswell, but I am still not sure if figured it out completly.

Here is an example of a Matrix solved by (what I believe to be) a Frontalsolver by Bruce Irons.
Steps:

  1. F0 is loaded and solved
  2. F0 is loaded back
  3. F1 is loaded and solved
  4. F1 is loaded back
  5. F2 is loaded and solved
  6. F2 is loaded back
Can someone please confirm if that is the Algorithm that is used in the Frontalsolver by Bruce Irons and correct me if necessary?

I have doubts because in other Algorithms (e.g. Multifrontalsolver) the Frontalmatrix is built by only using the first row and collum, and fill the rest with zeros.
  • It seems like you have two separate questions: 1. Can someone please confirm if that is the Algorithm that is used in the Frontalsolver by Bruce Irons and correct me if necessary? 2. Is that the Case with the "original" Frontalsolver by Bruce Irons as well?

  • I can help you answer this question, but it will involve some back and forth discussion in the comments. Also, this is not exactly a concrete math problem but more of a discussion and explanation of a methodology. I can give my best try to explain to you what is happening and refer you to references that explain in more detail.

  • I would ask to increase the bounty to $45 at least, because basically I will be answering questions untill you are satisfied.

  • I agree with Mathe. The bounty is too low for the level of the question.

  • Done. I hope one of you can help me :)

Answer

Answers can be viewed only if
  1. The questioner was satisfied and accepted the answer, or
  2. The answer was disputed, but the judge evaluated it as 100% correct.
View the answer
  • Thank you, that aleardy helped a lot. My last doubt about my example is if the frontalmatrix is "built" correctly". When looking at the Multifrontal Method by Duff and Reid, the Frontal matrix is formed only filling the first Row and Collum. The rest is filled with zeros. And I am not 100% sure if that isnt the case with the Frontalsolver by Irons. So the last thing I would need to know is that the Frontalmatrix isnt filled with any zeros like it is in the Multifrontalsolver.

  • I added an edit to my initial response so you can read it more clearly.

  • How I understand the frontalmatrix is built: Frontalsolver by Irons: like in the example pdf. if there are any zeros betwenn the nonzeros, they are included, thats why it applies best in banded matrices. Multifrontalsolver by Duff and Reid: The first frontalmatrix is built by taking only the nonzeros of the first row and collum and fill the rest with zeros. The first Frontalmatrix of the example would then look lik this: [11 12] [13 0]

  • https://juser.fz-juelich.de/record/45354/files/ib-2005-03.pdf On page 14 Formular 4.2 is what I meant by filled with zeros.

  • Equation 4.2 (a matrix with only zeros in the first row and column) is not present in "A frontal solution program for finite element analysis" by Bruce M. Irons.

  • I meant equation 4.2 in the pdf linked in the comment. Is there an example of a an actual matrix solved by both variants of the algorithm? I added another pdf where i solved a small matrix by what I believe is the Multifrontalsolver by Duff and Ried.

  • What I mean to say is that the idea or assumption that a matrix has only zeros in the first row and column of a front matrix is not present at all in "A frontal solution program for finite element analysis" by Bruce M. Irons.

  • Ok but, but how I understand it, it is in the Multifrontalsolver by Duff and Reid?

  • Also no. The idea or assumption that a matrix has only zeros in the first row and column of a front matrix is not present either in "The Multifrontal Solution of Indefinite Sparse Symmetric Linear" by I. S. Duff, and J. K. Reid. This is even explicit in Figure 3. (page 310) where they apply Multifrontal solution to a matrix with nonzero elements in the first row and first column.

  • The zeros are in alle rows and collums EXCEPT for the first row and collum. Those are filled with the non zero elements of those rows and collums from the original matrix.

  • First Frontal matrix: The first row is filled with with the non zero elements from the the first row of the original matrix. The first collum is filled with the Nonzeros of the first collum. The test is filled with zeros. That's what I meant.

  • I correct myself. It is not the case that zeros have to be everywhere except on the first row and column. Figure 3. on the paper exhibits elements off the first row and column in the Multifrontal solver paper. It's the same situation in the original Frontal solver by Irons.

  • But when you look at the 2nd pdf I posted, if you dont fill the frontal matrix with zeros (except for pivot row and collum), wouldnt that make it close to impossible to have it run multiple fronts at once?

  • You could eliminate entry (4,1) using entry (1,1) as pivot in one frontal matrix. Simultaneously, you could eliminate entry (7,2) using entry (2,2) as pivot in another appropriate frontal matrix and eliminate entry (6,3) using (3,3) as pivot in another frontal matrix. Taking care of recombining correctly, you would also eliminate entry (7,5) using entry (5,5) as pivot and recombining with the first frontal matrix result.

  • Thats exactly what I did. The thing is that Entries (7,2); (7,4); (7,5) amd (7,6) also changes entry (7,7) so how would they be assembled after being eliminated? Especially when (7,2) and (7,5) can be eliminated simultaneously.

  • I added an edit to show how to recombine matrices. Basically, you identify which operations to perform on each individual front, and then add those operations together to the end result.

  • Alright, Thanks a lot. You really saved me here.

The answer is accepted.