Message Boards Message Boards

Multinomial equations for factoring a sum of equal grade exterior products

Posted 5 years ago

I have a need to solve multinomial equations efficiently. It is part of an algorithm for factoring a sum of equal grade exterior products in n-space into a single product. The algorithm runs into efficiency problems when I get to 6 or 7 dimensional spaces and higher grades of exterior products. The Mathematica Solve routine is the time limiting part.

To illustrate a typical lower dimensional case, which is not an efficiency problem, I use the typical code:

canonicalEquations = {-a[1, 2] a[2, 1] + a[1, 1] a[2, 2] == 
   4, -a[1, 3] a[2, 1] + a[1, 1] a[2, 3] == 
   1, -a[1, 4] a[2, 1] + a[1, 1] a[2, 4] == 
   3, -a[1, 3] a[2, 2] + a[1, 2] a[2, 3] == 
   6, -a[1, 4] a[2, 2] + a[1, 2] a[2, 4] == 
   38, -a[1, 4] a[2, 3] + a[1, 3] a[2, 4] == 5}
solutions = Solve[canonicalEquations, MaxExtraConditions -> All]

I use the conditions to generate values for the free variables using a FindInstance statement.

This has 8 variables, 6 equations and 2 solutions. But a case in 6 dimensions might have 20 variables, 5 equations and 15 solutions.

I only need one solution so I'm wondering if there is a method to save time by generating only a single solution. Perhaps I could do that by specifying a specific set of variables to solve for but I don't know how to do that in advance.

I understand that the GroebnerBasis routine is used in Solve under the hood with multinomial equations but I'm only partly familiar with its use.

4 Replies

Is there some reason not to use FindInstance from the outset?

FindInstance[canonicalEquations == 0, 
 Variables[canonicalEquations]]

(* Out[298]= {{a[1, 1] -> -1, a[1, 2] -> 5, a[1, 3] -> 11/4, 
  a[1, 4] -> 53/4, a[2, 1] -> -1, a[2, 2] -> 1, a[2, 3] -> 7/4, 
  a[2, 4] -> 41/4}} *)
POSTED BY: Daniel Lichtblau

Many thanks Daniel, that works pretty well and is simpler. Trying to factor a 5-form in 7-dimensional space using Solve I aborted the calculation after 15 minutes. Using FindInstance took 6 seconds. A significant improvement!

using FindMinimum with an objective function of 0 and the canonicalEquations as constraints would give you a numerical solution to your equations.

POSTED BY: Frank Kampas

Thank you Frank. This method is somewhat problematic. It sometimes gives a solution but other times doesn't ( saying possible infeasibility detected) when I know there is a solution because the equations were generated from a factored case that was then expanded to give the input.

Also FindMinimum gives Real answers while Solve with give Integer or Rational answers with Integer input.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract