<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Courier New";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:3.0cm 2.0cm 3.0cm 2.0cm;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="DA" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D">Doug: Thanks a lot; I see the logic now! For my specific application the second argument is a sparse vector, but that modification should be straight forward
with more iterators (and they are definitely sorted). <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D">To the list: Does it have enough general interest to justify writing it up for the gallery?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D">Cheers<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D">Søren<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Courier New";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> dmbates@gmail.com [mailto:dmbates@gmail.com]
<b>On Behalf Of </b>Douglas Bates<br>
<b>Sent:</b> 25. marts 2014 16:51<br>
<b>To:</b> Søren Højsgaard<br>
<b>Cc:</b> rcpp-devel@lists.r-forge.r-project.org<br>
<b>Subject:</b> Re: [Rcpp-devel] RcppEigen: Avoiding accessing elements with coeff(i, j) in sparse matrix<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Two other small points. I am assuming that the set of indices in the second argument is sorted. Also, it would be best to declare the function as<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">bool foo(const MSpMat X, const Eigen::Map<Eigen::VectorXi> idx) as in the enclosed<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Tue, Mar 25, 2014 at 10:45 AM, Douglas Bates <<a href="mailto:bates@stat.wisc.edu" target="_blank">bates@stat.wisc.edu</a>> wrote:<o:p></o:p></p>
<div>
<p class="MsoNormal">The enclosed works on this example. The logic is to check each column in the index set for all the elements of the index set, except the one on the diagonal, being in the set of row indices. I have added some diagnostic output to demonstrate
the flow.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Tue, Mar 25, 2014 at 9:48 AM, Douglas Bates <<a href="mailto:bates@stat.wisc.edu" target="_blank">bates@stat.wisc.edu</a>> wrote:<o:p></o:p></p>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">On Tue, Mar 25, 2014 at 6:42 AM, Søren Højsgaard <<a href="mailto:sorenh@math.aau.dk" target="_blank">sorenh@math.aau.dk</a>> wrote:<o:p></o:p></p>
<p class="MsoNormal">Dear all,<br>
I have a large sparse adjacency matrix X for an undirected graph. For a subset 'idx' of the vertices I want to find out if the subgraph defined by this subset is complete (i.e. has edges between all variables). So in R, one would check if X[idx,idx] has only
ones outside the diagonal, but this is slow and I want to do it with Rcpp. Here is one attempt where I simply add up the elements above (or below) the diagonal, and to access the elements of X I use coeff which is relatively slow (because X is a sparse matrix).<br>
<br>
#include <RcppEigen.h><br>
typedef Eigen::MappedSparseMatrix<double> MSpMat;<br>
typedef Eigen::SparseVector<double> SpVec;<br>
typedef SpVec::InnerIterator InIter;<br>
<br>
//[[Rcpp::export]]<br>
double foo (MSpMat X, Eigen::VectorXi idx){<br>
SpVec sidx = idx.sparseView();<br>
double out=0;<br>
int i2, j2;<br>
for (InIter i_(sidx); i_; ++i_){<br>
i2 = i_.index();<br>
for (InIter j_(sidx); j_; ++j_){<br>
j2 = j_.index();<br>
if (i2>j2)<br>
out += X.coeff( i2, j2);<br>
}<br>
}<br>
return out;<br>
}<br>
<br>
/*** R<br>
library(Matrix)<br>
M1 <- new("dgCMatrix"<br>
, i = c(1L, 2L, 3L, 0L, 2L, 3L, 0L, 1L, 3L, 0L, 1L, 2L, 4L, 5L, 3L, 5L, 3L, 4L)<br>
, p = c(0L, 3L, 6L, 9L, 14L, 16L, 18L)<br>
, Dim = c(6L, 6L)<br>
, Dimnames = list(c("a", "b", "c", "d", "e", "f"), c("a", "b", "c", "d", "e", "f"))<br>
, x = c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)<br>
, factors = list()<br>
)<br>
M1<br>
<br>
foo(M1, c(2,3,4))<br>
<br>
*/<br>
Can anyone see a better way of doing this?<br>
<br>
I was thinking about whether the sparse matrix iterators could be a solution, but I can't a hold on it.
<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal">Sparse matrix inner and outer iterators are definitely the way to go. I'll write a version using them.<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal">I was also thinking about using sparse matrices in RcppArmadillo, but I guess the problem (speed) is the same (haven't tried!).<o:p></o:p></p>
</blockquote>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal" style="margin-bottom:12.0pt">Any advice will be greatly appreciated.<br>
Cheers<br>
Søren<br>
<br>
<br>
<br>
_______________________________________________<br>
Rcpp-devel mailing list<br>
<a href="mailto:Rcpp-devel@lists.r-forge.r-project.org" target="_blank">Rcpp-devel@lists.r-forge.r-project.org</a><br>
<a href="https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/rcpp-devel" target="_blank">https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/rcpp-devel</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>