(FEM) Reorder nodes or use sparse matrix storing techniquesEfficient assembly of finite element matrix in MATLABPreconditioner for finding the smallest eigenpairs of a large, but structured, matrixIs there a bound on the number of edges, facets, and elements in a 3D simplicial mesh in terms of the number of mesh nodes?Raviart-Thomas elements global definition and compact supportMeshing options to generate number of the sides of and element (tetgen-triangle)Applying the result of Cuthill-McKee in SciPyBoundary condtions on nonlinear FEM time integrationSparse matrix inverse with reduced bandwidthLeveraging scipy for matrix free finite elementsbit-packing and compression of data structures in scientific computing
Cryptography and elliptic curves
Is ‘despite that’ right?
Map extent same as grid for QGIS Atlas
What was the notion of limit that had Newton?
How to get the IP of a user who executed a command?
spatiotemporal regression
Why is the Sun made of light elements only?
We are two immediate neighbors who forged our own powers to form concatenated relationship. Who are we?
Hexagonal Grid Filling
Different problems with tabularx
How to efficiently lower your karma
How to compare d20+x with advantage to d20+y without advantage (x < y)
Company stopped paying my salary. What are my options?
Names of the Six Tastes
Succinct and gender-neutral Russian word for "writer"
My perfect evil overlord plan... or is it?
Whats the purpose of lockedLoadData / uncached page build takes around a minute, spent in usleep
What do "KAL." and "A.S." stand for in this inscription?
Why is it wrong to *implement* myself a known, published, widely believed to be secure crypto algorithm?
What does formal training in a field mean?
Why did they go to Dragonstone?
date -d 'previous Monday" to display the preceding Monday
Why does it take longer to fly from London to Xi'an than to Beijing
Translation of the latin word 'sit' in Thomas Aquinas' works
(FEM) Reorder nodes or use sparse matrix storing techniques
Efficient assembly of finite element matrix in MATLABPreconditioner for finding the smallest eigenpairs of a large, but structured, matrixIs there a bound on the number of edges, facets, and elements in a 3D simplicial mesh in terms of the number of mesh nodes?Raviart-Thomas elements global definition and compact supportMeshing options to generate number of the sides of and element (tetgen-triangle)Applying the result of Cuthill-McKee in SciPyBoundary condtions on nonlinear FEM time integrationSparse matrix inverse with reduced bandwidthLeveraging scipy for matrix free finite elementsbit-packing and compression of data structures in scientific computing
$begingroup$
Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because, since CSR/CSC only stores non-zero elements I guess reorder wouldn't be much advantageous.
finite-element sparse
edited Apr 30 at 15:38
Anton Menshov
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
$endgroup$
add a comment |
$begingroup$
Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because, since CSR/CSC only stores non-zero elements I guess reorder wouldn't be much advantageous.
finite-element sparse
edited Apr 30 at 15:38
Anton Menshov
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
$endgroup$
add a comment |
$begingroup$
Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because, since CSR/CSC only stores non-zero elements I guess reorder wouldn't be much advantageous.
finite-element sparse
edited Apr 30 at 15:38
Anton Menshov
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
$endgroup$
Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because, since CSR/CSC only stores non-zero elements I guess reorder wouldn't be much advantageous.
finite-element sparse
finite-element sparse
edited Apr 30 at 15:38
Anton Menshov
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
edited Apr 30 at 15:38
Anton Menshov
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
edited Apr 30 at 15:38
Anton Menshov
4,13721665
edited Apr 30 at 15:38
Anton Menshov
4,13721665
edited Apr 30 at 15:38
Anton Menshov
4,13721665
4,13721665
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
asked Apr 30 at 12:57
Gustavo CostaGustavo Costa
82
82
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.
Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
$endgroup$
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "363"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fscicomp.stackexchange.com%2fquestions%2f32543%2ffem-reorder-nodes-or-use-sparse-matrix-storing-techniques%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.
Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
$endgroup$
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
add a comment |
$begingroup$
You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.
Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
$endgroup$
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
add a comment |
$begingroup$
You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.
Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
$endgroup$
You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.
Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
answered Apr 30 at 13:12
rchilton1980rchilton1980
2,412713
2,412713
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
add a comment |
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs.
$endgroup$
– LedHead
Apr 30 at 17:15
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
$begingroup$
Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly.
$endgroup$
– rchilton1980
May 1 at 0:59
add a comment |
Thanks for contributing an answer to Computational Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fscicomp.stackexchange.com%2fquestions%2f32543%2ffem-reorder-nodes-or-use-sparse-matrix-storing-techniques%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
