Return to Question

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method" Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.

• V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable" Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to if it is possible to solve a system of linear equations by alternatively performing iterations of Newton's method on two groups of variables.

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method" Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.

• V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable" Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to if it is possible to solve a system of linear equations by alternatively performing iterations of Newton's method on two groups of variables.

• Śmietański, M. J. "A generalized Jacobian based Newton method for semismooth block-triangular system of equations" J. Comput. Appl. Math.. 2007. Solving block triagular system by newton iteration on each block can work. "We prove locally superlinear convergence of parameterized version method that is well defined even when the generalized Jacobian is singular."

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method" Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.

• V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable" Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to whether it is possible to solve a system of linear equations by dividing the variables into two groups.

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method" Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.

• V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable" Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to if it is possible to solve a system of linear equations by alternatively performing iterations of Newton's method on two groups of variables.

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009
• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method"

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

• A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

• B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations by Newton-like method" Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.

• V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable" Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to whether it is possible to solve a system of linear equations by dividing the variables into two groups.