Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

The algorithm is a branch-and-bound algorithm that calculates dominances for PRA, probalistic risk assessment. The task was to find faster ways to do it in numerical software such as Matlab but we found it extremely hard, more here. Now I am trying to find ways to speed it up in symbolic softwares such as Mathematica.

The algorithm uses multilinearity but not with respect to constant term. The worst case time scenario with respect to basic events is exponential. This does not mean that it is exponential with respect to minimal cut sets. It is a method to analyse the impact of epistemic uncertainty about event probabilities in fault tree analysis. The algo is based on a theorem in multilinear optimization according to which the extreme values of multilinear function $f: HR \rightarrow \mathbb R$ are attained at the vertices of HR where HR is a hyperrectangle in $\mathbb R^n$. Basically the idea of this algo is to traverse the corners in the hyperrectangle. So:

what kind of methods would you use to speed up this kind of recursive algorithm?

Algorithm

Algo[f0_, lb0_, ub0_] := 
  Module[{f = f0, lb = lb0, ub = ub0, monomials, fp, fm, bvar, blb, 
    bub}, If[f == 0 || f == 0.0, Return[True]];
   monomials = f // MonomialList;
   fp = Select[monomials*1.0*D, (First[#] >= 0) &] /. {D -> 1};
   fm = Select[monomials*1.0*D, (First[#] < 0) &] /. {D -> 1};
   If[Plus @@ (fp /. lb) + Plus @@ (fm /. ub) >= 0, Return[True]];
   If[Plus @@ (fp /. ub) + Plus @@ (fm /. lb) < 0, Return[False]];
   bvar = Variables[f] // First;
   blb = Select[lb, ((# // First) == bvar) &];
   bub = Select[ub, ((# // First) == bvar) &];
   Algo[(f /. blb), lb, ub] \[And] Algo[(f /. bub), lb, ub]];

Example how to use this function

Algo[Subscript[p, 1] + Subscript[p, 2] - Subscript[p, 1] Subscript[p, 2], 
 Table[Subscript[p, i] -> 0.01, {i, 7}], Table[Subscript[p, i] -> 0.04, {i, 7}]]
share|improve this question
2  
It would help if you give some example where the function is noticably slow (perhaps a larger one than the one you gave). –  Leonid Shifrin Apr 9 '13 at 20:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.