0
$\begingroup$

How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the

min(i; j) - 1,

because I have no idea, what the author wanted to say by it. I know that it means " choose the lesser number of 'i' and 'j' and then substract one", but I don't know what is I and J here (maybe coordinates of the current task? Or is it written from the task's point of view, so the whole pseudocode runs at every task?) etc.

The whole presentation with this code (slide 12) is here.

Pseudocode and diagram of tasks

code

Bigger picture here.

Improve this question
$\endgroup$
3
  • $\begingroup$ The code on the right is running on node $i, j$ of the graph on the left. $i$ is the row and $j$ is the column. Note that this part of the code also seems to be running only on the nodes in the lower-triangular part of the matrix. (Nodes below the diagonal have a variable $l_{ij}$ where nodes on and above the diagonal have a variable $u_{ij}$ instead.) $\endgroup$
    – Wandering Logic
    Commented Feb 3, 2015 at 12:43
  • $\begingroup$ So it's running on every node in the lower-triangular part, is it? $\endgroup$
    – Eenoku
    Commented Feb 3, 2015 at 13:32
  • $\begingroup$ Please transcribe the pseudocode using Markdown formatting, and give a close crop of the graph image. $\endgroup$
    – Raphael
    Commented Mar 1, 2015 at 12:54

1 Answer 1

Reset to default
0
$\begingroup$

It will be clearer if you look at 1 slide before (10/42). The algorithm does not decide on how do you assign to node. It just says that the algorithm can be consisted of many parallel tasks. Each task has identification of $(i,j)$ and each executes the algorithm in slide (12/42).

More specifically, each task is assigned an entry $a_{ij}$ of the matrix ($n^2$ number of tasks), and at the end of the algorithm that entry becomes $u_{ij}$ if $i \le j$ or $l_{ij}$ if $i>j$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.