Re: Question about sparsity-based implementation in MATPower

[Abhyankar, Shrirang G.]

Hi Shruti,
  The direct linear solver used by MATLAB depends on the symmetry of the 
Jacobian matrix. For MATPOWER test cases that have symmetric Jacobians (due to 
inactive taps), a Cholesky factorization is used (LL^T = A). For cases that 
lead to non-symmetric Jacobian, MATLAB uses UMFPACK for performing the linear 
solve.

Shri

From: Shruti Rao >
Reply-To: MATPOWER discussion forum 
>
Date: Sunday, October 18, 2015 at 5:37 PM
To: MATPOWER discussion forum 
>
Subject: Question about sparsity-based implementation in MATPower

Greetings MATPower community,

I had a question about the way sparsity-based techniques are used in the 
Newton-Raphson solver of the power flow algorithm in MATPower.

I ran the code step-by-step and from my understanding, the way the sparsity of 
the Jacobian matrix is exploited is that it is created as a MATLAB "sparse" 
matrix wherein only the non-zeros are stored with the respective matrix 
positions and then the MATLAB operator "\" is invoked while calculating dx = 
-(J \ F); where J is the Jacobian and F is the vector of mismatches.

MATLAB "\" by default exploits the sparsity of the matrix by using a LU solver. 
The kind of solver "\" uses actually depends on the matrix structure if it is 
diagonal/tridiagonal/banded and so on (Flowchart obtained from Mathworks 
website attached in the email). I assume based on the typical  structure of the 
Jacobian that an LU solver is most likely to be chosen.

Is my understanding correct or am I missing something out? Thank you for your 
time and effort.


--
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116

Question about sparsity-based implementation in MATPower

[Shruti Rao]

Greetings MATPower community,

I had a question about the way sparsity-based techniques are used in the
Newton-Raphson solver of the power flow algorithm in MATPower.

I ran the code step-by-step and from my understanding, the way the sparsity
of the Jacobian matrix is exploited is that it is created as a MATLAB
"sparse" matrix wherein only the non-zeros are stored with the respective
matrix positions and then the MATLAB operator "\" is invoked while
calculating dx = -(J \ F); where J is the Jacobian and F is the vector of
mismatches.

MATLAB "\" by default exploits the sparsity of the matrix by using a LU
solver. The kind of solver "\" uses actually depends on the matrix
structure if it is diagonal/tridiagonal/banded and so on (Flowchart
obtained from Mathworks website attached in the email). I assume based on
the typical  structure of the Jacobian that an LU solver is most likely to
be chosen.

Is my understanding correct or am I missing something out? Thank you for
your time and effort.


-- 
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116

Re: Question about sparsity-based implementation in MATPower

[Shruti Rao]

Thank you Dr. Abhyakar,

My main aim was to confirm that MATPower uses the inbuilt "\" to solve the
matrix equations and not Tinney or some other form of reordering  and then
LU factorization followed by forward,backward substitutions. From your
response I assume that it is true that MATpower uses "\" right?

Thank you for your response.



On Sun, Oct 18, 2015 at 6:27 PM, Abhyankar, Shrirang G. 
wrote:

> Hi Shruti,
>   The direct linear solver used by MATLAB depends on the symmetry of the
> Jacobian matrix. For MATPOWER test cases that have symmetric Jacobians (due
> to inactive taps), a Cholesky factorization is used (LL^T = A). For cases
> that lead to non-symmetric Jacobian, MATLAB uses UMFPACK for performing the
> linear solve.
>
> Shri
>
> From: Shruti Rao 
> Reply-To: MATPOWER discussion forum 
> Date: Sunday, October 18, 2015 at 5:37 PM
> To: MATPOWER discussion forum 
> Subject: Question about sparsity-based implementation in MATPower
>
> Greetings MATPower community,
>
> I had a question about the way sparsity-based techniques are used in the
> Newton-Raphson solver of the power flow algorithm in MATPower.
>
> I ran the code step-by-step and from my understanding, the way the
> sparsity of the Jacobian matrix is exploited is that it is created as a
> MATLAB "sparse" matrix wherein only the non-zeros are stored with the
> respective matrix positions and then the MATLAB operator "\" is invoked
> while calculating dx = -(J \ F); where J is the Jacobian and F is the
> vector of mismatches.
>
> MATLAB "\" by default exploits the sparsity of the matrix by using a LU
> solver. The kind of solver "\" uses actually depends on the matrix
> structure if it is diagonal/tridiagonal/banded and so on (Flowchart
> obtained from Mathworks website attached in the email). I assume based on
> the typical  structure of the Jacobian that an LU solver is most likely to
> be chosen.
>
> Is my understanding correct or am I missing something out? Thank you for
> your time and effort.
>
>
> --
> Best Regards,
> Shruti Dwarkanath Rao
>
> Graduate Research Assistant
> School of Electrical, Computer and Energy Engineering
> Arizona State University
> Tempe, AZ, 85281
> 650 996 0116
>
>


-- 
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116

Re: Question about sparsity-based implementation in MATPower

[Abhyankar, Shrirang G.]

Shruti,
  MATPOWER does use “\” operator for the linear solves. However note that, 
internally, MATLAB does perform some sort of matrix reordering to reduce the 
fill-ins in the factored matrix. For instance, UMFPACK uses an approximate 
minimum degree reordering scheme by default.

Shri

From: Shruti Rao >
Reply-To: MATPOWER discussion forum 
>
Date: Sunday, October 18, 2015 at 8:31 PM
To: MATPOWER discussion forum 
>
Subject: Re: Question about sparsity-based implementation in MATPower

Thank you Dr. Abhyakar,

My main aim was to confirm that MATPower uses the inbuilt "\" to solve the 
matrix equations and not Tinney or some other form of reordering  and then LU 
factorization followed by forward,backward substitutions. From your response I 
assume that it is true that MATpower uses "\" right?

Thank you for your response.



On Sun, Oct 18, 2015 at 6:27 PM, Abhyankar, Shrirang G. 
> wrote:
Hi Shruti,
  The direct linear solver used by MATLAB depends on the symmetry of the 
Jacobian matrix. For MATPOWER test cases that have symmetric Jacobians (due to 
inactive taps), a Cholesky factorization is used (LL^T = A). For cases that 
lead to non-symmetric Jacobian, MATLAB uses UMFPACK for performing the linear 
solve.

Shri

From: Shruti Rao >
Reply-To: MATPOWER discussion forum 
>
Date: Sunday, October 18, 2015 at 5:37 PM
To: MATPOWER discussion forum 
>
Subject: Question about sparsity-based implementation in MATPower

Greetings MATPower community,

I had a question about the way sparsity-based techniques are used in the 
Newton-Raphson solver of the power flow algorithm in MATPower.

I ran the code step-by-step and from my understanding, the way the sparsity of 
the Jacobian matrix is exploited is that it is created as a MATLAB "sparse" 
matrix wherein only the non-zeros are stored with the respective matrix 
positions and then the MATLAB operator "\" is invoked while calculating dx = 
-(J \ F); where J is the Jacobian and F is the vector of mismatches.

MATLAB "\" by default exploits the sparsity of the matrix by using a LU solver. 
The kind of solver "\" uses actually depends on the matrix structure if it is 
diagonal/tridiagonal/banded and so on (Flowchart obtained from Mathworks 
website attached in the email). I assume based on the typical  structure of the 
Jacobian that an LU solver is most likely to be chosen.

Is my understanding correct or am I missing something out? Thank you for your 
time and effort.


--
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116



--
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116

Re: Question about sparsity-based implementation in MATPower

[Shruti Rao]

Thank you Dr. Abhyankar for the guidance. I appreciate your time and effort.

Shruti

On Sun, Oct 18, 2015 at 10:02 PM, Abhyankar, Shrirang G. 
wrote:

> Shruti,
>   MATPOWER does use “\” operator for the linear solves. However note that,
> internally, MATLAB does perform some sort of matrix reordering to reduce
> the fill-ins in the factored matrix. For instance, UMFPACK uses an
> approximate minimum degree reordering scheme by default.
>
> Shri
>
> From: Shruti Rao 
> Reply-To: MATPOWER discussion forum 
> Date: Sunday, October 18, 2015 at 8:31 PM
> To: MATPOWER discussion forum 
> Subject: Re: Question about sparsity-based implementation in MATPower
>
> Thank you Dr. Abhyakar,
>
> My main aim was to confirm that MATPower uses the inbuilt "\" to solve the
> matrix equations and not Tinney or some other form of reordering  and then
> LU factorization followed by forward,backward substitutions. From your
> response I assume that it is true that MATpower uses "\" right?
>
> Thank you for your response.
>
>
>
> On Sun, Oct 18, 2015 at 6:27 PM, Abhyankar, Shrirang G. 
> wrote:
>
>> Hi Shruti,
>>   The direct linear solver used by MATLAB depends on the symmetry of the
>> Jacobian matrix. For MATPOWER test cases that have symmetric Jacobians (due
>> to inactive taps), a Cholesky factorization is used (LL^T = A). For cases
>> that lead to non-symmetric Jacobian, MATLAB uses UMFPACK for performing the
>> linear solve.
>>
>> Shri
>>
>> From: Shruti Rao 
>> Reply-To: MATPOWER discussion forum 
>> Date: Sunday, October 18, 2015 at 5:37 PM
>> To: MATPOWER discussion forum 
>> Subject: Question about sparsity-based implementation in MATPower
>>
>> Greetings MATPower community,
>>
>> I had a question about the way sparsity-based techniques are used in the
>> Newton-Raphson solver of the power flow algorithm in MATPower.
>>
>> I ran the code step-by-step and from my understanding, the way the
>> sparsity of the Jacobian matrix is exploited is that it is created as a
>> MATLAB "sparse" matrix wherein only the non-zeros are stored with the
>> respective matrix positions and then the MATLAB operator "\" is invoked
>> while calculating dx = -(J \ F); where J is the Jacobian and F is the
>> vector of mismatches.
>>
>> MATLAB "\" by default exploits the sparsity of the matrix by using a LU
>> solver. The kind of solver "\" uses actually depends on the matrix
>> structure if it is diagonal/tridiagonal/banded and so on (Flowchart
>> obtained from Mathworks website attached in the email). I assume based on
>> the typical  structure of the Jacobian that an LU solver is most likely to
>> be chosen.
>>
>> Is my understanding correct or am I missing something out? Thank you for
>> your time and effort.
>>
>>
>> --
>> Best Regards,
>> Shruti Dwarkanath Rao
>>
>> Graduate Research Assistant
>> School of Electrical, Computer and Energy Engineering
>> Arizona State University
>> Tempe, AZ, 85281
>> 650 996 0116
>>
>>
>
>
> --
> Best Regards,
> Shruti Dwarkanath Rao
>
> Graduate Research Assistant
> School of Electrical, Computer and Energy Engineering
> Arizona State University
> Tempe, AZ, 85281
> 650 996 0116
>
>


-- 
Best Regards,
Shruti Dwarkanath Rao

Graduate Research Assistant
School of Electrical, Computer and Energy Engineering
Arizona State University
Tempe, AZ, 85281
650 996 0116