An even faster solver for general systems of equations
Identifieur interne : 001410 ( Istex/Corpus ); précédent : 001409; suivant : 001411An even faster solver for general systems of equations
Auteurs : Christian Fecht ; Helmut SeidlSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.
Url:
DOI: 10.1007/3-540-61739-6_42
Links to Exploration step
ISTEX:F7740819D607C7BD061760F6AC0A8A775D41E521Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An even faster solver for general systems of equations</title><author><name sortKey="Fecht, Christian" sort="Fecht, Christian" uniqKey="Fecht C" first="Christian" last="Fecht">Christian Fecht</name><affiliation><mods:affiliation>Universität des Saarlandes, Postfach 151150, D-66041, Saarbrücken</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fecht@cs.uni-sb.de</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@psi.uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F7740819D607C7BD061760F6AC0A8A775D41E521</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/3-540-61739-6_42</idno><idno type="url">https://api.istex.fr/document/F7740819D607C7BD061760F6AC0A8A775D41E521/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001410</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001410</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An even faster solver for general systems of equations</title><author><name sortKey="Fecht, Christian" sort="Fecht, Christian" uniqKey="Fecht C" first="Christian" last="Fecht">Christian Fecht</name><affiliation><mods:affiliation>Universität des Saarlandes, Postfach 151150, D-66041, Saarbrücken</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fecht@cs.uni-sb.de</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@psi.uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1996</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">F7740819D607C7BD061760F6AC0A8A775D41E521</idno><idno type="DOI">10.1007/3-540-61739-6_42</idno><idno type="ChapterID">14</idno><idno type="ChapterID">Chap14</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Christian Fecht</name><affiliations><json:string>Universität des Saarlandes, Postfach 151150, D-66041, Saarbrücken</json:string><json:string>E-mail: fecht@cs.uni-sb.de</json:string></affiliations></json:item><json:item><name>Helmut Seidl</name><affiliations><json:string>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</json:string><json:string>E-mail: seidl@psi.uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.</abstract><qualityIndicators><score>6.608</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>846</abstractCharCount><pdfWordCount>6568</pdfWordCount><pdfCharCount>33003</pdfCharCount><pdfPageCount>16</pdfPageCount><abstractWordCount>134</abstractWordCount></qualityIndicators><title>An even faster solver for general systems of equations</title><chapterId><json:string>14</json:string><json:string>Chap14</json:string></chapterId><refBibs><json:item><author><json:item><name>F Bourdoncle</name></json:item></author><host><volume>2</volume><issue>4</issue><author></author><title>Journal of Functional Programming</title><publicationDate>1992</publicationDate></host><title>Abstract Interpretation by Dynamic Partitioning</title><publicationDate>1992</publicationDate></json:item><json:item><host><author><json:item><name>B </name></json:item><json:item><name>Le Charlier</name></json:item><json:item><name>P Van Hentenryck</name></json:item></author><title>A Universal Top-Down Fixpoint Algorithm</title><publicationDate>1992</publicationDate></host></json:item><json:item><author><json:item><name>B </name></json:item><json:item><name>Le Charlier</name></json:item><json:item><name>P Van Hentenryck</name></json:item></author><host><volume>16</volume><pages><last>101</last><first>35</first></pages><issue>1</issue><author></author><title>TOPLAS</title><publicationDate>1994</publicationDate></host><title>Experimental evaluation of a generic abstract interpretation algorithm for Prolog</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>R Cleaveland</name></json:item><json:item><name>B Steffen</name></json:item></author><host><author></author><title>CAV'91</title><publicationDate>1991</publicationDate></host><title>A Linear-Time Model Checking Algorithm for the Alternation-Free Modal Mu-Calculus</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>A Cortesi</name></json:item><json:item><name>G Fil~</name></json:item><json:item><name>W Winsborough</name></json:item></author><host><pages><last>327</last><first>322</first></pages><author></author><title>LICS'91</title><publicationDate>1991</publicationDate></host><title>Prop revisited: Propositional formulas as abstract domain for groundness analysis</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>P Cousot</name></json:item><json:item><name>R Cousot</name></json:item></author><host><pages><last>252</last><first>238</first></pages><author></author><title>POPL'77</title><publicationDate>1977</publicationDate></host><title>Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints</title><publicationDate>1977</publicationDate></json:item><json:item><author><json:item><name>P Cousot</name></json:item><json:item><name>R Cousot</name></json:item></author><host><volume>13</volume><pages><last>179</last><first>103</first></pages><issue>2</issue><author></author><title>Journal of Logic Programming</title><publicationDate>1992</publicationDate></host><title>Abstract Interpretation and Application to Logic Programs</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>A Dicky</name></json:item></author><host><volume>46</volume><pages><last>303</last><first>285</first></pages><author></author><title>TCS</title><publicationDate>1986</publicationDate></host><title>An Algebraic and Algorithmic Method of Analysing Transition Systems</title><publicationDate>1986</publicationDate></json:item><json:item><author><json:item><name>Christian Fecht</name></json:item></author><host><pages><last>419</last><first>418</first></pages><author></author><title>SAS'95</title><publicationDate>1995</publicationDate></host><title>GENA -a Tool for Generating Prolog Analyzers from Specifications</title><publicationDate>1995</publicationDate></json:item><json:item><host><author><json:item><name>M,S Hecht</name></json:item></author><title>Flow Analysis of Computer Programs</title><publicationDate>1977</publicationDate></host></json:item><json:item><author><json:item><name>S Horwitz</name></json:item><json:item><name>A Demers</name></json:item><json:item><name>T Teitelbaum</name></json:item></author><host><volume>24</volume><pages><last>694</last><first>679</first></pages><author></author><title>Acta Informatica</title><publicationDate>1987</publicationDate></host><title>An Efficient General Iteration Algorithm for Dataflow Analysis</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>N J0rgensen</name></json:item></author><host><pages><last>345</last><first>329</first></pages><author></author><title>SAS'94</title><publicationDate>1994</publicationDate></host><title>Finding Fixpoints in Finite Function Spaces Using Neededness Analysis and Chaotic Iteration</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>G,A </name></json:item></author><host><pages><last>206</last><first>194</first></pages><author></author><title>POPL'73</title><publicationDate>1973</publicationDate></host><title>A Unified Approach to Global Program Optimization</title><publicationDate>1973</publicationDate></json:item><json:item><author><json:item><name>K Marriott</name></json:item><json:item><name>H Sondergaard</name></json:item><json:item><name>N,D Jones</name></json:item></author><host><volume>16</volume><pages><last>648</last><first>607</first></pages><issue>3</issue><author></author><title>ACM Transactions of Programming Languages and Systems</title><publicationDate>1994</publicationDate></host><title>Denotational Abstract Interpretation of Logic Programs</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>M Sharir</name></json:item><json:item><name>A Pnueli</name></json:item></author><host><pages><last>233</last><first>189</first></pages><author></author><title>Program Flow Analysis: Theory and Application</title><publicationDate>1981</publicationDate></host><title>Two approaches to interprocedural data flow analysis</title><publicationDate>1981</publicationDate></json:item><json:item><host><pages><last>278</last><first>237</first></pages><author><json:item><name>P Van Hentenryck</name></json:item><json:item><name>A Cortesi</name></json:item><json:item><name>B. Le Charlier</name></json:item></author><title>Evaluation of the domain Prop. The Journal o] Logic Programming</title><publicationDate>1995</publicationDate></host></json:item><json:item><author><json:item><name>B Vergauwen</name></json:item><json:item><name>J Wauman</name></json:item><json:item><name>J Lewi</name></json:item></author><host><pages><last>328</last><first>314</first></pages><author></author><title>SAS'94</title><publicationDate>1994</publicationDate></host><title>Efficient fixpoint computation</title><publicationDate>1994</publicationDate></json:item><json:item><host><author><json:item><name>R Wilhelm</name></json:item><json:item><name>D Maurer</name></json:item></author><title>Compiler Construction</title><publicationDate>1995</publicationDate></host></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1996</copyrightDate></serie><host><editor><json:item><name>Radhia Cousot</name></json:item><json:item><name>David A. Schmidt</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Programming Techniques</value></json:item><json:item><value>Software Engineering</value></json:item><json:item><value>Programming Languages, Compilers, Interpreters</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item></subject><isbn><json:string>978-3-540-61739-6</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Static Analysis</title><bookId><json:string>3540617396</json:string></bookId><volume>1145</volume><pages><last>204</last><first>189</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-70674-8</json:string></eisbn><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-61739-6</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-61739-6_42</json:string></doi><id>F7740819D607C7BD061760F6AC0A8A775D41E521</id><score>0.45990747</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/F7740819D607C7BD061760F6AC0A8A775D41E521/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/F7740819D607C7BD061760F6AC0A8A775D41E521/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/F7740819D607C7BD061760F6AC0A8A775D41E521/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">An even faster solver for general systems of equations</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1996</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">An even faster solver for general systems of equations</title><author xml:id="author-1"><persName><forename type="first">Christian</forename><surname>Fecht</surname></persName><email>fecht@cs.uni-sb.de</email><affiliation>Universität des Saarlandes, Postfach 151150, D-66041, Saarbrücken</affiliation></author><author xml:id="author-2"><persName><forename type="first">Helmut</forename><surname>Seidl</surname></persName><email>seidl@psi.uni-trier.de</email><affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</affiliation></author></analytic><monogr><title level="m">Static Analysis</title><title level="m" type="sub">Third International Symposium, SAS '96 Aachen, Germany, September 24–26, 1996 Proceedings</title><idno type="pISBN">978-3-540-61739-6</idno><idno type="eISBN">978-3-540-70674-8</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-61739-6</idno><idno type="book-ID">3540617396</idno><idno type="book-title-ID">45062</idno><idno type="book-volume-number">1145</idno><idno type="book-chapter-count">28</idno><editor><persName><forename type="first">Radhia</forename><surname>Cousot</surname></persName></editor><editor><persName><forename type="first">David</forename><forename type="first">A.</forename><surname>Schmidt</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-02"></date><biblScope unit="volume">1145</biblScope><biblScope unit="page" from="189">189</biblScope><biblScope unit="page" to="204">204</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1996</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">F7740819D607C7BD061760F6AC0A8A775D41E521</idno><idno type="DOI">10.1007/3-540-61739-6_42</idno><idno type="ChapterID">14</idno><idno type="ChapterID">Chap14</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I14010</label><label>I14029</label><label>I14037</label><label>I1603X</label><label>I16048</label><item><term>Computer Science</term></item><item><term>Programming Techniques</term></item><item><term>Software Engineering</term></item><item><term>Programming Languages, Compilers, Interpreters</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Mathematical Logic and Formal Languages</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-02">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/F7740819D607C7BD061760F6AC0A8A775D41E521/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540617396</BookID><BookTitle>Static Analysis</BookTitle><BookSubTitle>Third International Symposium, SAS '96 Aachen, Germany, September 24–26, 1996 Proceedings</BookSubTitle><BookVolumeNumber>1145</BookVolumeNumber><BookDOI>10.1007/3-540-61739-6</BookDOI><BookTitleID>45062</BookTitleID><BookPrintISBN>978-3-540-61739-6</BookPrintISBN><BookElectronicISBN>978-3-540-70674-8</BookElectronicISBN><BookChapterCount>28</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I14010" Priority="1" Type="Secondary">Programming Techniques</BookSubject><BookSubject Code="I14029" Priority="2" Type="Secondary">Software Engineering</BookSubject><BookSubject Code="I14037" Priority="3" Type="Secondary">Programming Languages, Compilers, Interpreters</BookSubject><BookSubject Code="I1603X" Priority="4" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16048" Priority="5" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Radhia</GivenName><FamilyName>Cousot</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><GivenName>A.</GivenName><FamilyName>Schmidt</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap14" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>14</ChapterID><ChapterDOI>10.1007/3-540-61739-6_42</ChapterDOI><ChapterSequenceNumber>14</ChapterSequenceNumber><ChapterTitle Language="En">An even faster solver for general systems of equations</ChapterTitle><ChapterCategory>Contributed Papers</ChapterCategory><ChapterFirstPage>189</ChapterFirstPage><ChapterLastPage>204</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>2</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540617396</BookID><BookTitle>Static Analysis</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Christian</GivenName><FamilyName>Fecht</FamilyName></AuthorName><Contact><Email>fecht@cs.uni-sb.de</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Helmut</GivenName><FamilyName>Seidl</FamilyName></AuthorName><Contact><Email>seidl@psi.uni-trier.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>Universität des Saarlandes</OrgName><OrgAddress><Postbox>Postfach 151150</Postbox><Postcode>D-66041</Postcode><City>Saarbrücken</City></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Fachbereich IV - Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We present a new algorithm which computes a partial approximate solution for a system of equations. It is <Emphasis Type="Italic">local</Emphasis> in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is <Emphasis Type="Italic">generic</Emphasis> in that it makes no assumptions on the application domain, and it is <Emphasis Type="Italic">general</Emphasis> in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution.</Para><Para>The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>An even faster solver for general systems of equations</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>An even faster solver for general systems of equations</title></titleInfo><name type="personal"><namePart type="given">Christian</namePart><namePart type="family">Fecht</namePart><affiliation>Universität des Saarlandes, Postfach 151150, D-66041, Saarbrücken</affiliation><affiliation>E-mail: fecht@cs.uni-sb.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Helmut</namePart><namePart type="family">Seidl</namePart><affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</affiliation><affiliation>E-mail: seidl@psi.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-02</dateIssued><copyrightDate encoding="w3cdtf">1996</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.</abstract><relatedItem type="host"><titleInfo><title>Static Analysis</title><subTitle>Third International Symposium, SAS '96 Aachen, Germany, September 24–26, 1996 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Radhia</namePart><namePart type="family">Cousot</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">David</namePart><namePart type="given">A.</namePart><namePart type="family">Schmidt</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I14010">Programming Techniques</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic><topic authority="SpringerSubjectCodes" authorityURI="I14037">Programming Languages, Compilers, Interpreters</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic></subject><identifier type="DOI">10.1007/3-540-61739-6</identifier><identifier type="ISBN">978-3-540-61739-6</identifier><identifier type="eISBN">978-3-540-70674-8</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">45062</identifier><identifier type="BookID">3540617396</identifier><identifier type="BookChapterCount">28</identifier><identifier type="BookVolumeNumber">1145</identifier><part><date>1996</date><detail type="volume"><number>1145</number><caption>vol.</caption></detail><extent unit="pages"><start>189</start><end>204</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><identifier type="istex">F7740819D607C7BD061760F6AC0A8A775D41E521</identifier><identifier type="DOI">10.1007/3-540-61739-6_42</identifier><identifier type="ChapterID">14</identifier><identifier type="ChapterID">Chap14</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1996</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001410 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001410 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:F7740819D607C7BD061760F6AC0A8A775D41E521
|texte= An even faster solver for general systems of equations
}}
| This area was generated with Dilib version V0.6.31. |  |