স্পার্স ম্যাট্রিক্স টেকনিক ও কম্পিউটেশনাল কমপ্লেক্সিটি

import random

random.seed(42)

n = 12  # n x n ম্যাট্রিক্স
density = 0.12  # প্রায় ১২% এন্ট্রি ননজিরো রাখা হচ্ছে

dense = [[0.0]*n for _ in range(n)]
nonzero_count = 0
for i in range(n):
    for j in range(n):
        if random.random() < density:
            dense[i][j] = round(random.uniform(1.0, 9.0), 2)
            nonzero_count += 1

print(f"n = {n}, মোট এন্ট্রি = {n*n}, ননজিরো এন্ট্রি = {nonzero_count}")
print(f"স্পার্সিটি (জিরো এন্ট্রির ভগ্নাংশ) = {1 - nonzero_count/(n*n):.4f}")

dense_stored_numbers = n*n

# COO (coordinate list) স্পার্স রিপ্রেজেন্টেশন: (row, col, value)-এর লিস্ট
coo = []
for i in range(n):
    for j in range(n):
        if dense[i][j] != 0.0:
            coo.append((i, j, dense[i][j]))

coo_stored_numbers = len(coo) * 3  # প্রতিটি এন্ট্রিতে row, col, value -- ৩টি সংখ্যা
print(f"COO-তে সংরক্ষিত এন্ট্রি: {len(coo)} টি টাপল -> মোট {coo_stored_numbers} টি সংখ্যা (row,col,value)")
print(f"ডেন্স সংরক্ষিত সংখ্যা: {dense_stored_numbers}")
print(f"স্টোরেজ অনুপাত (COO/dense): {coo_stored_numbers/dense_stored_numbers:.4f}")

# DOK (dictionary of keys) রিপ্রেজেন্টেশন
dok = {}
for i in range(n):
    for j in range(n):
        if dense[i][j] != 0.0:
            dok[(i, j)] = dense[i][j]
print(f"DOK-তে সংরক্ষিত এন্ট্রি: {len(dok)} টি key-value জোড়া")

# ---- ম্যাট্রিক্স-ভেক্টর গুণ: ডেন্স বনাম স্পার্স, প্রকৃত মাল্টিপ্লাই-অপারেশন গণনা ----
x = [round(random.uniform(-2.0, 2.0), 2) for _ in range(n)]

def dense_matvec(M, v):
    result = [0.0]*len(M)
    mult_ops = 0
    for i in range(len(M)):
        s = 0.0
        for j in range(len(v)):
            s += M[i][j] * v[j]
            mult_ops += 1
        result[i] = s
    return result, mult_ops

def sparse_matvec_coo(coo_list, v, num_rows):
    result = [0.0]*num_rows
    mult_ops = 0
    for (i, j, val) in coo_list:
        result[i] += val * v[j]
        mult_ops += 1
    return result, mult_ops

dense_result, dense_ops = dense_matvec(dense, x)
sparse_result, sparse_ops = sparse_matvec_coo(coo, x, n)

max_diff = max(abs(a-b) for a, b in zip(dense_result, sparse_result))
print()
print(f"ডেন্স matvec-এর মাল্টিপ্লাই-অপারেশন: {dense_ops}")
print(f"স্পার্স (COO) matvec-এর মাল্টিপ্লাই-অপারেশন: {sparse_ops}")
print(f"অপারেশন হ্রাসের অনুপাত: {dense_ops/sparse_ops:.2f}x কম মাল্টিপ্লাই")
print(f"ডেন্স ও স্পার্স ফলাফলের সর্বোচ্চ পার্থক্য (~0 হওয়া উচিত): {max_diff:.2e}")