liu.seSearch for publications in DiVA

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt146",{id:"formSmash:upper:j_idt146",widgetVar:"widget_formSmash_upper_j_idt146",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt147_j_idt149",{id:"formSmash:upper:j_idt147:j_idt149",widgetVar:"widget_formSmash_upper_j_idt147_j_idt149",target:"formSmash:upper:j_idt147:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

A greedy algorithm for the optimal basis problemPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 1997 (English)In: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 37, no 3, 591-599 p.Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 1997. Vol. 37, no 3, 591-599 p.
##### Keyword [en]

Optimal basis problem; the Hadamard condition number; minimum spanning tree problem; greedy algorithm; secant approximation of derivatives; interpolation methods
##### National Category

Computational Mathematics
##### Identifiers

URN: urn:nbn:se:liu:diva-78866DOI: 10.1007/BF02510241OAI: oai:DiVA.org:liu-78866DiVA: diva2:536299
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt437",{id:"formSmash:j_idt437",widgetVar:"widget_formSmash_j_idt437",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt443",{id:"formSmash:j_idt443",widgetVar:"widget_formSmash_j_idt443",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt449",{id:"formSmash:j_idt449",widgetVar:"widget_formSmash_j_idt449",multiple:true});
Available from: 2012-06-21 Created: 2012-06-21 Last updated: 2017-12-07

The following problem is considered. Given *m*+1 points {*x* _{i }}_{0} ^{m }in *R* ^{n }which generate an *m*-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form *x* _{i }−*x* _{j }. This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrix *f*′ of a nonlinear mapping*f* by using values of*f* computed at *m*+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination of *m* pairs {*x* _{i },*x* _{j }}. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm in *O*(*m* ^{2}) time. The complexity of this reduction is equivalent to one *m×n* matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is below *O*(*n* ^{2.376}) for *m=n*. Applications of the algorithm to interpolation methods are discussed.

doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1151",{id:"formSmash:j_idt1151",widgetVar:"widget_formSmash_j_idt1151",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1210",{id:"formSmash:lower:j_idt1210",widgetVar:"widget_formSmash_lower_j_idt1210",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1211_j_idt1213",{id:"formSmash:lower:j_idt1211:j_idt1213",widgetVar:"widget_formSmash_lower_j_idt1211_j_idt1213",target:"formSmash:lower:j_idt1211:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});