2
$\begingroup$

The system of equations is the following: $$ \Gamma_i^{\ -1} = \sum_{i=1}^nA_{ij}\Gamma_j, $$ where $\Gamma = (\Gamma_i)$ is a vector of size $n$ and $A$ is a matrix of size $n\times n$, with $n \gt 100$.

So there is a paper (Numerical and computational aspects of cosmo-based activity coefficient models, Brazilian Journal of Chemical Engineering vol.36 no.1) showing, that successive substitution is faster than Newton–Raphson if solved as mentioned above.

I was wondering if through some kind of linear algebra change the system of equations becomes easier/faster to solve?

I don't know if it helps, but here is how the matrix $A$ is calculated (Hadamard product): $$ A = B \circ D $$ Where $B$ is symmetric, dense with only positive (and negative) entries and $D$ is dense with only positive entries and all rows are the same and their sum is 1.

I just corrected that $B$ is positive symmetric, and since $D$ is also positive, this would make $A$ positive. So: $$ A_{ij}>0 $$

Improve this question
$\endgroup$
18
  • 1
    $\begingroup$ For large systems, Newton methods will be very poor until you are fairly close to the minimizing point. My suspicion is that the fastest method will look (1) good heuristic for initial guess, (2) fast first-order method for a few steps, and then (3) Newton iterations till convergence. Due to your additional structure it might be possible to do more rigorously than this, of course, but generally it's pretty difficult to rigorously analyze such nonlinear systems. $\endgroup$
    – Christopher A. Wong
    Commented Jan 3, 2021 at 10:18
  • 1
    $\begingroup$ @ChristopherA.Wong Comments are meant to suggest improvements to the question. Yours is a perfectly fine answer, in my view, not a comment. Posting this kind of content as comments defeats the purpose of the reputation and upvotes system, and I think it is bad practice on SE. $\endgroup$
    – Federico Poloni
    Commented Jan 3, 2021 at 10:46
  • 1
    $\begingroup$ ...and why do you give these hints or outline answers as comments, exactly? I don't know where the practice started, but it seems a misuse of the system to me. These "hints" cannot be downvoted even when they are completely wrong. $\endgroup$
    – Federico Poloni
    Commented Jan 4, 2021 at 8:14
  • 1
    $\begingroup$ @Federico Mostly because I don't care about gaining rep points, and I would spend too long writing a detailed answer, more than I should. It's either give some information in a comment, or none at all. $\endgroup$
    – David Roberts ♦
    Commented Jan 4, 2021 at 10:11
  • 2
    $\begingroup$ I'd suggest to write the same information as an answer instead, even without adding details. In this way it can be accepted, for instance, downvoted if it's wrong, searched using the MO search box, edited for corrections (for instance automated fixes to dead links), etc. There are many details that simply don't work with comments. $\endgroup$
    – Federico Poloni
    Commented Jan 4, 2021 at 13:08

1 Answer 1

Reset to default
2
$\begingroup$

Based on what I know of similar equations, I would expect that you can't beat this "successive substitution" (essentially a non-linear Gauss-Seidel) in case where it converges fast and only few iterations are needed.

However, there are choices of the parameters for which NGS requires many iterations (when the Jacobian is close to being a singular matrix, more precisely), and then Newton (on the formulation $\operatorname{diag}(\Gamma)A\Gamma-\mathbf{1}=0$, as it is done in the paper) will become the winner.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have to calculate the Jacobian numerically, so this makes it quite slow. (look at the paper link I added in the original question) $\endgroup$
    – Simon
    Commented Jan 3, 2021 at 10:26
  • $\begingroup$ @Simon You solve the linear system of equations in (6), right? I wouldn't call it "calculating the Jacobian numerically"; anyhow, that costs $O(n^3)$, it's normal that it is much slower than an $O(n^2)$ iteration of the nonlinear Gauss-Seidel method. Newton takes the cake in cases when you need many iterations of the NGS method. $\endgroup$
    – Federico Poloni
    Commented Jan 3, 2021 at 10:30
  • $\begingroup$ So basically, it is already as efficient as I can get? $\endgroup$
    – Simon
    Commented Jan 3, 2021 at 10:32
  • $\begingroup$ @Simon For this kind of problem, I'd guess so, but it also depends on how much accuracy you need. As Christopher Wong suggests in a comment, it's a good idea to focus on the starting point instead, if you have to solve many of these problems. $\endgroup$
    – Federico Poloni
    Commented Jan 3, 2021 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .