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

Question

$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:

F0 is loaded and solved
F0 is loaded back
F1 is loaded and solved
F1 is loaded back
F2 is loaded and solved
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.

Linear Algebra Matrices

Matthias Emanuel Slomeus

12

Matchmaticians Frontal solver by Bruce Irons? Am I using the right Algorithm here? File #1

File #1 (pdf)

Matchmaticians Frontal solver by Bruce Irons? Am I using the right Algorithm here? File #2

File #2 (pdf)

Report

Mathe

0

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?
Mathe

0

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.
Mathe

0

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

0

I agree with Mathe. The bounty is too low for the level of the question.
Matthias Emanuel Slomeus

0

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

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Mathe

0

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?
Mathe

0

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.
Mathe

0

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

0

I agree with Mathe. The bounty is too low for the level of the question.
Matthias Emanuel Slomeus

0

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

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

Introduction

I found this reference (which can be found in libgen) that I believe is very on point on explaining how Frontalsolver works and how it relates to the original work of Bruce Irons:

Duff, Iain S., Erisman, A. M., Reid, John Ker. Direct methods for sparse matrices Oxford University Press (2017)

In short, the algorithm you describe is indeed the Frontalsolver proposed by Irons, with some small caveats:

1. The original work by Irons was designed for symmetric, definite positive and in the context of finite-element problems.

What this means is that Irons original work is meant for linear systems $Ax=b$ that decompose as: $A = \sum_i A_i$, $x = \sum_i x_i$, where $A_i$'s are sparse matrices that only incorporate a few unknowns ($x_i$'s) and are symmetric and positive definite.

In this sense, the seminal work is different from the algorithm you describe. Because your algorithm assumes a totally assembled (not decomposed) matrix $A$ from the very beggining, that is not even symmetric or definite positive.

In the reference that I cite, they describe the frontal method for finite-element problems in section 11.10 with an example. My best advise is to read the example and see for yourself how they apply the same Frontalface method you referenced in their example.

2. Frontalsolver, however, can be generally applied to a wider range of matrices (not necessarily symmetric, for example) and problems (not just linear problems).

In section 11.12 they describe how frontal methods can be applied in more general problems. For example, in the algorithm you described (unlike Irons), the matrices don't need to be symmetric. Also, one does not need to limit this 'Frontalface' idea to linear systems but can also applying for finding appropriate pivots in matrices.

If you have any questions or would like me to address something more concrete, please let me know.

---------------------------------------------------------------------------------------------------
Edit 1:

Could you clarify what you mean by "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"?

The fundamental difference between the Frontalsolver and the Multifrontalsolver is that the first only deals with one frontal matrix at a time, incorporating variables (with its corresponding rows and columns) in blocks into the Frontal matrix moving along the diagonal. This means variables enter the frontal matrix in the same order as they appear are originally in the linear system.

The Multifrontalsolver on the other hand, deals with separate frontal matrices at the same time, as long as each frontal matrix fully contains all the equations from the variables that conform it.

Equations 12.2.1 to 12.2.3 (in the cited reference) make this distinction clearer. The difference is in the way matrices are assembled: either following the natural ordering of the variables/blocks along the diagonal (Frontsolver) or following a tree orderding along independent blocks in the system.

The contents of the assembly blocks, or whether the first row or column of the original system is filled with zeros is not an assumption in either the Frontsolver or Multifrontal solver. There is of course sparsity in the original system which facilitates and permits a 'Front matrix' strategy.

Whether the Front matrices move along the diagonal or they are applied along independent blocks of the original system is the only difference betweem these two methods.

---------------------------------------------------------------------------------------------------
Edit 2:

How to recombine matrices. Next is a toy example to show how matrices can be recombined. Basically, we just add all operations to the end result.

Suppose we have the system:

4	0	2
0	3	1
8	3	6

We can eliminate (3,1) using (1,1) as pivot and eliminate (3,2) using (2,2) as pivot.

The operation to eliminate (3,1) would be to sum to (-8/4) times row I to row III.

The operation to eliminate (3,2) would be to sum to (-3/3) times row II to row III.

We perform thos operations simultaneously, knowing that two elements will be eliminated from this, so we only compute (3,3) and (3,4). The computation for (3,3) is trivial so we only show the computation for (3,4):

6 <- 6 + (-8/4)*2 + (-3/3)*1 = 1

The resulting matrix is then:

4	0	2
0	3	1
0	0	1

Mathe

3.5K

Matthias Emanuel Slomeus

0

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.
Mathe

0

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

0

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]
Matthias Emanuel Slomeus

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.
Mathe

0

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.
Matthias Emanuel Slomeus

0

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.
Mathe

0

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.
Matthias Emanuel Slomeus

0

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

0

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.
Matthias Emanuel Slomeus

0

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.
Matthias Emanuel Slomeus

0

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.
Mathe

0

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.
Matthias Emanuel Slomeus

0

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?
Mathe

0

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.
Matthias Emanuel Slomeus

0

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.
Mathe

0

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.
Matthias Emanuel Slomeus

0

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

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

Answer

Related Questions

Search