An alternate for Householder QR linear equation solving for fixed-layout sparse matrix
$begingroup$
This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver.
For smaller than 5, I use a direct inverse computation, but for problems that are bigger, I currently use a simple dense Householder pivot solver, which get slows really quickly.
I can optimize the layout of the matrix as well, but I'm not sure "usual" sparse matrix solving method could be applied here and if they could be faster than brute-force Householder QR. I feel that knowing the sparsity could be leveraged to solve the problem faster.
linear-algebra numerical-optimization sparse-matrices
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
$endgroup$
add a comment |
$begingroup$
This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver.
For smaller than 5, I use a direct inverse computation, but for problems that are bigger, I currently use a simple dense Householder pivot solver, which get slows really quickly.
I can optimize the layout of the matrix as well, but I'm not sure "usual" sparse matrix solving method could be applied here and if they could be faster than brute-force Householder QR. I feel that knowing the sparsity could be leveraged to solve the problem faster.
linear-algebra numerical-optimization sparse-matrices
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
$endgroup$
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37
add a comment |
$begingroup$
This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver.
For smaller than 5, I use a direct inverse computation, but for problems that are bigger, I currently use a simple dense Householder pivot solver, which get slows really quickly.
I can optimize the layout of the matrix as well, but I'm not sure "usual" sparse matrix solving method could be applied here and if they could be faster than brute-force Householder QR. I feel that knowing the sparsity could be leveraged to solve the problem faster.
linear-algebra numerical-optimization sparse-matrices
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
$endgroup$
This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver.
For smaller than 5, I use a direct inverse computation, but for problems that are bigger, I currently use a simple dense Householder pivot solver, which get slows really quickly.
I can optimize the layout of the matrix as well, but I'm not sure "usual" sparse matrix solving method could be applied here and if they could be faster than brute-force Householder QR. I feel that knowing the sparsity could be leveraged to solve the problem faster.
linear-algebra numerical-optimization sparse-matrices
linear-algebra numerical-optimization sparse-matrices
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
edited Dec 2 '18 at 21:12
Matthieu Brucher
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
asked Dec 2 '18 at 20:58
Matthieu BrucherMatthieu Brucher
1063
1063
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37
add a comment |
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3023183%2fan-alternate-for-householder-qr-linear-equation-solving-for-fixed-layout-sparse%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3023183%2fan-alternate-for-householder-qr-linear-equation-solving-for-fixed-layout-sparse%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
$begingroup$
"Householder pivot solver"? I know gaussian pivoting and Householder QR, which one is it? Why do you think "usual" sparse solvers would not work? Have you tried? Also a nice feature of iterative methods is you can reuse the preceding solution as a starting point (likely useful in a process that is supposed to be convergent).
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:07
$begingroup$
@Jean-ClaudeArbaut Indeed, Householder QR (using Eigen implementation). I'm not sure because I want something faster than dense, and iterative seems contradictory. Still, if you want to implement a sparse iterative solver for something like 4-5 entries per row and columns, what would you go for?
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:14
$begingroup$
Since you are using Eigen: eigen.tuxfamily.org/dox/group__TopicSparseSystems.html
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:16
$begingroup$
By the way, I didn't notice the numerical-optimization tag: you may have a look at L-BFGS or sparseLM.
$endgroup$
– Jean-Claude Arbaut
Dec 2 '18 at 21:29
$begingroup$
Good pointers, thanks. I usually have only a couple of iterations, but LBFGS may be worth it indeed.
$endgroup$
– Matthieu Brucher
Dec 2 '18 at 21:37