在 Chapel 中构建稀疏热带极限函数

Question

给定矩阵 A 和 B 热带乘积被定义为通常的矩阵乘积，乘法换算成加法，加法换算成 minimum。也就是说，它 returns 一个新矩阵 C 这样，

C_ij = minimum(A_ij, B_ij, A_i1 + B_1j, A_i2 + B_12,..., A_im + B_mj)

给定图 g 的基础邻接矩阵 A_g，关于热带乘积的 nth "power" 表示节点之间最多可到达的连接n 步。也就是说，如果节点 i 和 j 由 m<=n 条边分隔，则 C_ij = (A**n)_ij 的值为 m。

一般来说，给定一些具有 N 个节点的图。图的直径最多只能是N；并且，给定一个直径为 k、所有 n>k 为 A**n = A**k 的图，矩阵 D_ij = A**k 称为 "distance matrix" 条目，表示所有节点之间的距离图形。

我在 chapel 中编写了一个热带产品函数，我想编写一个采用邻接矩阵和 returns 结果距离矩阵的函数。我尝试了以下方法无济于事。非常感谢克服这些错误的指导！

proc tropicLimit(A:[] real,B:[] real) {
 var R = tropic(A,B);
 if A == R {
   return A;
 } else {
   tropicLimit(R,B);
 }
}

引发域不匹配错误，因此我进行了以下编辑：

proc tropicLimit(A:[] real,B:[] real) {
 var R = tropic(A,B);
 if A.domain == R.domain {
   if && reduce (A == R) {
     return R;
   } else {
     tropicLimit(R,B);
   }
 } else {
   tropicLimit(R,B);
 }
}

抛出

src/MatrixOps.chpl:602: error: control reaches end of function that returns a value

proc tropicLimit(A:[] real,B:[] real) {
 var R = tropic(A,B);
 if A.domain == R.domain {
   if && reduce (A == R) {  // Line 605 is this one
   } else {
     tropicLimit(R,B);
   }
 } else {
   tropicLimit(R,B);
 }
return R;
}

让我回到这个错误

src/MatrixOps.chpl:605: error: halt reached - Sparse arrays can't be zippered with anything other than their domains and sibling arrays (CS layout)

我也试过在 break 条件下使用 for 循环，但这也不起作用

proc tropicLimit(B:[] real) {
 var R = tropic(B,B);
 for n in B.domain.dim(2) {
   var S = tropic(R,B);
   if S.domain != R.domain {
    R = S; // Intended to just reassign the handle "R" to the contents of "S" i.o.w. destructive update of R
   } else {
     break;
   }   
 }
 return R;
}

有什么建议吗？

Answer 1

src/MatrixOps.chpl:605: error: halt reached - Sparse arrays can't be zippered with anything other than their domains and sibling arrays (CS layout)

我相信您在当前实现中遇到了压缩稀疏数组的限制，记录在 #6577 中。

从等式中删除一些未知数，我相信这个经过提炼的代码片段演示了您遇到的问题：

use LayoutCS;

var dom = {1..10, 1..10};

var Adom: sparse subdomain(dom) dmapped CS();
var Bdom: sparse subdomain(dom) dmapped CS();

var A: [Adom] real;
var B: [Bdom] real;

Adom += (1,1);
Bdom += (1,1);

A[1,1] = 1.0;
B[1,1] = 2.0;


writeln(A.domain == B.domain); // true
var willThisWork = && reduce (A == B);
// dang.chpl:19: error: halt reached - Sparse arrays can't be zippered with
//           anything other than their domains and sibling arrays (CS layout)

作为 work-around，我建议在确认域相等并执行 && reduce 后循环遍历稀疏索引。这是你可以包装在辅助函数中的东西，例如

proc main() { 
  var dom = {1..10, 1..10};

  var Adom: sparse subdomain(dom) dmapped CS();
  var Bdom: sparse subdomain(dom) dmapped CS();

  var A: [Adom] real;
  var B: [Bdom] real;

  Adom += (1,1);
  Bdom += (1,1);

  A[1,1] = 1.0;
  B[1,1] = 2.0;

  if A.domain == B.domain {
    writeln(equal(A, B));
  }
}

/* Some day, this should be A.equals(B) ! */
proc equal(A: [], B: []) {
  // You could also return 'false' if domains do not match
  assert(A.domain == B.domain);

  var s = true;

  forall (i,j) in A.domain with (&& reduce s) {
    s &&= (A[i,j] == B[i,j]);
  }

  return s;
}

src/MatrixOps.chpl:602: error: control reaches end of function that returns a value

此错误是由于未在每种情况下都返回某些内容而导致的。我相信你打算这样做：

proc tropicLimit(A:[] real,B:[] real) {
 var R = tropic(A,B);
 if A.domain == R.domain {
   if && reduce (A == R) {
     return R;
   } else {
     return tropicLimit(R,B);
   }
 } else {
   return tropicLimit(R,B);
 }
}

在 Chapel 中构建稀疏热带极限函数

Constructing a Sparse Tropical Limit Function in Chapel

graph

sparse-matrix

hpc

convergence

chapel