On Producing Multiple Solutions Using Repeated Trials |
| |
Authors: | Frans M. Coetzee Virginia L. Stonick |
| |
Affiliation: | (1) Siemens Corporate Research, Princeton, NJ 08540, USA;(2) ECE Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
Abstract: | The number of trials that is required by an algorithm to produce a given fraction of the problem solutions with a specified level of confidence is analyzed. The analysis indicates that the number of trials required to find a large fraction of the solutions rapidly decreases as the number of solutions obtained on each trial by an algorithm increases. In applications where multiple solutions are sought, this decrease in the number of trials could potentially offset the additional computational cost of algorithms that produce multiple solutions on a single trial. The analysis framework presented is used to compare the efficiency of a homotopy algorithm to that of a Newton method by measuring both the number of trials and the number of calculations required to obtain a specified fraction of the solutions. |
| |
Keywords: | Exhaustive solution methods Homotopy methods Repeated trials |
本文献已被 SpringerLink 等数据库收录! |