রৈখিক বীজগণিতের মূল বিষয় মধ্যে

রৈখিক বীজগণিতের মূল বিষয় সম্পর্কে

"লিনিয়ার অ্যালজেবরা" কী?

এর প্রচুর টেকনিক্যাল সংজ্ঞা আছে, Wikipedia-তে, পাঠ্যবইয়ে, আর 3Blue1Brown-এর মতো দুর্দান্ত সব ওয়েবসাইটে। তবে আমাদের উদ্দেশ্যে আমরা আরও সহজভাবে বলতে পারি।

Julia (আর Python)-এর মেইনটেইনাররা এই ধরনের জিনিস ভালোবাসেন। Exercism ম্যানেজমেন্ট অবশ্য ততটা নয়।

এই কনসেপ্টটি বিশাল একটি বিষয়ের সহজ দিকগুলোতেই সীমাবদ্ধ থাকবে। তবে সাবধান: এটি অনিবার্যভাবে বেশ গাণিতিক একটি কনসেপ্ট।

ভেক্টর কী?

এটা নির্ভর করে আপনি কাকে জিজ্ঞেস করছেন, আর বরং বিমূর্ত একটা জিনিসকে আপনি কীভাবে ভিজুয়ালাইজ করতে চান তার উপর।

• Julia-তে Vector{T} আসলে Array{T, 1}-এরই একটি অ্যালিয়াস, আর eltype T যেকোনো কিছু হতে পারে।
• ফিজিক্সে (অনেকাংশে) ভেক্টর হলো N-মাত্রিক স্পেসে একটি তির, যার একটি length আর একটি direction থাকে, কিন্তু কোনো নির্দিষ্ট অবস্থান থাকে না।
• লিনিয়ার অ্যালজেবরায় ফিজিক্সের ওই তিরটি স্পেসে স্থির থাকে, তার লেজ থাকে মূলবিন্দুতে। এতে তিরটির কাণ্ড অপ্রয়োজনীয় হয়ে যায়, তাই আমরা ভেক্টরটিকে N-মাত্রিক স্পেসে একটি point হিসেবে প্রকাশ করতে পারি, যেখানে Nটি এলিমেন্ট মূলবিন্দু থেকে Nটি অক্ষ বরাবর দূরত্ব নির্দেশ করে।

এখানে আমাদের উদ্দেশ্যে স্ট্রিং বা ক্যারেক্টারের ভেক্টর বাদ দিন। এই কনসেপ্টে আমরা সংখ্যাবাচক টাইপ নিয়ে কাজ করব: Int, Float, বা Complex।

ম্যাট্রিক্স কী?

এখানেও আপনি নানা রকম উত্তর পাবেন।

• সংখ্যার একটি আয়তাকার 2-D অ্যারে (যার কোনো এলোমেলো প্রান্ত নেই)। বর্গ ম্যাট্রিক্স এর একটি কমন বিশেষ রূপ।
• পাশাপাশি সাজানো কলাম ভেক্টরের একটি linear combination।
• একটি transformation, যাকে ভেক্টরের উপর প্রয়োগ করা যায়, ঠিক যেমন অন্য ইনপুট টাইপের উপর একটি function প্রয়োগ করা হয়।

কিছু ধরনের বর্গ ম্যাট্রিক্স এতটাই কমন যে তাদের আলাদা নাম আছে।

ডায়াগোনাল ম্যাট্রিক্স: সব অশূন্য এন্ট্রি থাকে main diagonal-এ (উপরের বাম কোণ থেকে নিচের ডান কোণ)।

julia> [1 0 0; 0 2 0; 0 0 3]
3×3 Matrix{Int64}:
 1  0  0
 0  2  0
 0  0  3

# a convenient shortcut
julia> diagm(1:3)
3×3 Matrix{Int64}:
 1  0  0
 0  2  0
 0  0  3

আইডেন্টিটি ম্যাট্রিক্স: এমন একটি ডায়াগোনাল ম্যাট্রিক্স যার কর্ণে কেবল এক থাকে (কারণটা পরে আরও স্পষ্ট হবে)। প্রায়ই এর সংক্ষিপ্ত রূপ I লেখা হয়।

julia> Matrix{Float64}(I, 3, 3)
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

আপার ট্রায়াঙ্গুলার: কর্ণে ও তার উপরে অশূন্য মান, নিচে শূন্য। লোয়ার ট্রায়াঙ্গুলার নিজেই অনুমান করে নিতে পারবেন।

ম্যাট্রিক্স ট্রান্সপোজ করা

আপনি যদি সত্যিই সারি আর কলাম অদলবদল করতে চান, permutedims() ফাংশনটি সেটাই করবে আর আপনাকে একটি নতুন ম্যাট্রিক্স দেবে।

এতে কপি করা জড়িত, যা বড় ম্যাট্রিক্স নিয়ে কাজ করার সময় ধীর আর মেমরি-সাপেক্ষ।

লিনিয়ার অ্যালজেবরার কাজে transpose() ফাংশনটি বেশি কাজের, কারণ এটি দ্রুত মূল ম্যাট্রিক্সের চারপাশে একটি লেজি র্যাপার তৈরি করে।

আরও কাজের হলো adjoint() ফাংশন, যা জটিল সংখ্যার কাল্পনিক অংশের চিহ্নও উল্টে দেয় (এটা কেন এত গুরুত্বপূর্ণ ভাবছেন? একটি দ্রুত উত্তর: কোয়ান্টাম মেকানিক্স)। এই অপারেশনটি এতটাই কমন যে অ্যাডজয়েন্ট তৈরি করতে আমরা কেবল ভ্যারিয়েবলের নামের শেষে একটি অ্যাপোস্ট্রফি ' যোগ করে দিতে পারি।

julia> m
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

# new, full copy
julia> permutedims(m)
3×2 Matrix{Int64}:
 1  4
 2  5
 3  6

# lazy version
julia> transpose(m)
3×2 transpose(::Matrix{Int64}) with eltype Int64:
 1  4
 2  5
 3  6

julia> mc = [1+2im 2+3im; 3+2im 1+2im]
2×2 Matrix{Complex{Int64}}:
 1+2im  2+3im
 3+2im  1+2im

# lazy conjugate transpose
julia> adjoint(mc)
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
 1-2im  3-2im
 2-3im  1-2im

# syntactic sugar for adjoint
julia> mc'
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
 1-2im  3-2im
 2-3im  1-2im

গুণ

এই ডকুমেন্টের বাকি অংশে LinearAlgebra মডিউলের ফাংশনালিটি আছে। একটি using LinearAlgebra লাইন এটি নেমস্পেসে নিয়ে আসবে, তবে উদাহরণগুলোতে আমরা এটি বারবার লিখব না (দেখতে খুব এলোমেলো লাগে)।

ভেক্টর, এলিমেন্ট-ভিত্তিক গুণফল

এটা ভেক্টর অপারেশনস কনসেপ্টে আলোচনা করা হয়েছে। অপারেটরটি হলো .*, যা ইনপুট ভেক্টরগুলোর উপর জোড়ায় জোড়ায় কাজ করে, আর ইনপুটের মতোই সাইজ ও টাইপের একটি আউটপুট দেয়।

julia> [1, 2] .* [3, 4]
2-element Vector{Int64}:
 3
 8

ভেক্টর, ডট প্রোডাক্ট

এই অত্যন্ত কমন অপারেশনটি পাঠ্যবইয়ে u ⋅ v হিসেবে লেখা হয়, আর একে "ডট" প্রোডাক্ট বলা হয়।

একটি ডট প্রোডাক্ট এলিমেন্ট-ভিত্তিক গুণফলের সমষ্টির সমান।

সাধারণ * অপারেটর দিয়ে দুটি ভেক্টর গুণ করা যায়, তবে কেবল তখনই যদি বাম দিকের ভেক্টরটি একটি adjoint হয়: সুবিধাজনকভাবে এটি u' * v লেখা হয়। ম্যাট্রিক্স গুণের পরের অংশে এটা আরও স্পষ্ট হবে।

উপরের (মাঝখানের) ডটটি Julia-তে পাওয়া যায় (\cdot লিখে tab), dot() ফাংশনের সিনট্যাকটিক সুগার হিসেবে। এখানে অ্যাডজয়েন্ট আলাদা করে উল্লেখ করার দরকার নেই, কারণ এই ব্যাপারটা স্বয়ংক্রিয়ভাবে সামলে নেওয়া হয়।

julia> using LinearAlgebra

# with element-wise syntax
julia> sum([1, 2] .* [3, 4])
11

# with u' * v syntax
julia> [1, 2]' * [3, 4]
11

# with dot()
julia> dot([1, 2], [3, 4])
11

# with \cdot syntax
julia> [1, 2] ⋅ [3, 4]
11

জটিল-মানের ভেক্টরের ক্ষেত্রে বাম দিকের ভেক্টরটি কনজুগেট হতে হবে (কাল্পনিক অংশের চিহ্ন উল্টে দেওয়া)। dot ফাংশন এটি স্বয়ংক্রিয়ভাবে করে, u' সিনট্যাক্স এটি স্পষ্টভাবে করে, কিন্তু u আর v জটিল হলে sum(u .* v) ফেল করবে।

ভেক্টর, ক্রস প্রোডাক্ট

অতীতে যারা একবার ইলেকট্রিসিটি অ্যান্ড ম্যাগনেটিজম কোর্স করেছেন, তাদের জন্য একটুখানি নস্টালজিয়া! আর যেসব ইঞ্জিনিয়ার টর্ক বা অ্যাঙ্গুলার মোমেন্টাম ভেক্টর হিসাব করতে জানেন, তাদের জন্যও।

ডট প্রোডাক্ট দুটি ভেক্টরকে একটি scalar-এ পরিণত করে, আর ক্রস প্রোডাক্ট দুটি 3-ভেক্টরকে তৃতীয় একটি 3-ভেক্টরে পরিণত করে।

ভেক্টর স্পেসের জ্যামিতিক উপস্থাপনায় নতুন ভেক্টরটি দুটি ইনপুট ভেক্টর ধারণ করা তলের লম্ব। দুটি ইনপুট সমান্তরাল হলে (চিহ্ন পর্যন্ত), তারা কোনো তল তৈরি করে না, ফলে আউটপুট হবে [0, 0, 0]।

ক্রম গুরুত্বপূর্ণ: u × v == -(v × u)। এটাই বিখ্যাত রাইট-হ্যান্ড রুল, যার কারণে আমাদের অনেকেই বুড়ো আঙুল আর দুটি আঙুল শূন্যে ঘোরাতে ঘোরাতে সেগুলোর দিকে তাকিয়ে থাকি (প্রায়ই বিভ্রান্ত মুখে)।

# with \times syntax
julia> [1, 2, 3] × [3, 4, 5]
3-element Vector{Int64}:
 -2
  4
 -2
# with cross()
julia> cross([1, 2, 3], [3, 4, 5])
3-element Vector{Int64}:
 -2
  4
 -2

লক্ষ্য করুন, এই অপারেশনটি length-3 ভেক্টরে সীমাবদ্ধ (অর্থাৎ অর্থোগোনাল x, y, z অক্ষযুক্ত ইউক্লিডীয় স্পেসের সমতুল্য)। গণিতবিদেরা অন্য মাত্রার জন্যও এটি সংজ্ঞায়িত করতে খুশিই, আর ফল হিসেবে আসে দুর্জ্ঞেয় এক শব্দের জটলা (হায়ার-অর্ডার টেনসর, ওয়েজ প্রোডাক্ট, এক্সটেরিয়র প্রোডাক্ট, মাল্টিভেক্টর...)। তখন আমাদের বেশিরভাগই পালিয়ে যাই বা দ্রুত বিষয় বদলে ফেলি!

নর্ম

একটি ভেক্টর কতটা "বড়"?

norm হলো এটা ধরার একটি চেষ্টা, ভেক্টরটিকে উপযুক্ত একটি স্কেলারে নামিয়ে এনে।

নর্মের পুরো একটি পরিবারই সংজ্ঞায়িত, তবে অনেকাংশে সবচেয়ে কমন হলো 2-নর্ম, যা √(v ⋅ v)।

এই রুট-মিন-স্কয়ার অপারেশনটি মূলবিন্দু থেকে পিথাগোরীয় দূরত্ব (N-মাত্রিক স্পেসে)। আমরা যদি ভেক্টরটিকে একটি তির হিসেবে ভাবি, যার লেজ মূলবিন্দুতে, তবে 2-নর্ম হলো তিরটির দৈর্ঘ্য।

দ্বিতীয় আর্গুমেন্ট হিসেবে p দিয়ে যেকোনো p-নর্ম হিসাব করা যায়। 1-নর্ম মাঝে মাঝে কাজে লাগে: এটি কেবল এন্ট্রিগুলোর পরম মানের সমষ্টি (তাই হিসাব করা খুব দ্রুত আর সহজ)।

# defaults to the 2-norm
julia> norm([1, 2, 3])
3.7416573867739413
# the 1-norm
julia> norm([1, -2, 3], 1)
6.0

ম্যাট্রিক্স গুণ

মনে হয়, পৃথিবীর প্রতিটি ফলিত গণিতবিদ গত ৮০ বছরের অনেকটা সময় ব্যয় করেছেন প্রতিটি হিসাবকে ম্যাট্রিক্স গুণের ধারায় পরিণত করতে।

এটি এমন একটি অপারেশন যা কম্পিউটার খুব ভালো পারে:

• এটি অত্যন্ত পুনরাবৃত্তিমূলক।
• এটি দক্ষতার সাথে প্যারালালাইজ করা যায়।
• এটি দ্রুততর করতে অনেক বিশেষায়িত হার্ডওয়্যার তৈরি হয়েছে, ১৯৭০-এর দশকের ৮ কোটি ডলারের Cray-1 থেকে শুরু করে আপনার ল্যাপটপে যে GPU সম্ভবত বসানোই আছে সেটি পর্যন্ত।

বিবরণটা বেশ সহজ, যদিও প্রথম দেখায় খুব একটা সহজবোধ্য লাগে না।

ভাবুন A ম্যাট্রিক্স একটি v ভেক্টরকে গুণ করে একটি w আউটপুট দিচ্ছে (লিনিয়ার অ্যালজেবরার রীতি অনুযায়ী, ম্যাট্রিক্সের জন্য বড় হাতের অক্ষর আর ভেক্টরের জন্য ছোট হাতের অক্ষর ব্যবহার করব)।

A-এর উপরের সারিকে v-এর সাথে ডট করে w-এর প্রথম এলিমেন্ট পাওয়া যায়, দ্বিতীয় সারি দেয় দ্বিতীয় এলিমেন্ট, এভাবে নিচে চলতে থাকে।

julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4
julia> v = [5, 6]
2-element Vector{Int64}:
 5
 6
julia> A * v
2-element Vector{Int64}:
 17  # equals [1, 2] ⋅ [5, 6]
 39  # equals [3, 4] ⋅ [5, 6]

ম্যাট্রিক্স * ম্যাট্রিক্স গুণ এটি ডান দিকের ম্যাট্রিক্সের সব কলাম জুড়ে বিস্তার করে।

C = A * B-এর ক্ষেত্রে আমরা ভাবতে পারি, A B-এর প্রতিটি কলামকে গুণ করে C-এর সংশ্লিষ্ট কলাম দেয়: অর্থাৎ ম্যাট্রিক্স-ভেক্টর গুণের একটি ধারা।

সমতুল্যভাবে বলা যায়, A-এর প্রথম সারিকে B-এর প্রতিটি কলামের সাথে ডট করে C-এর প্রথম সারি পাওয়া যায়, দ্বিতীয় সারি দেয় দ্বিতীয় সারি, এভাবে নিচে।

এমন বেশ কয়েকটি মানসিক মডেল আছে, আর আগ্রহী শিক্ষার্থীরা এগুলো নিয়ে আলোচনা করা একটি পুরো MIT লেকচার দেখতে পারেন।

julia> A
2×2 Matrix{Int64}:
 1  2
 3  4

julia> B = [5 7; 6 8]
2×2 Matrix{Int64}:
 5  7
 6  8

# left column is the same as A*v previously
julia> A * B
2×2 Matrix{Int64}:
 17  23
 39  53

julia> B * A
2×2 Matrix{Int64}:
 26  38
 30  44

উপরের উদাহরণে দেখা যায়, ম্যাট্রিক্স গুণ কমিউট করে না: A*B আর B*A-এর মধ্যে কোনো সরল সম্পর্ক নেই।

ম্যাট্রিক্স গুণ যাদের কাছে একেবারে নতুন, তাদের কাছে শুধু লেখা পড়ে এটি ভিজুয়ালাইজ করা সম্ভবত কঠিন। YouTube-এ এটি গ্রাফিক্যালি দেখানোর অনেক ভিডিও আছে, তাই "matrix multiplication" লিখে সার্চ করুন আর আপনার পছন্দের স্টাইল, বিস্তারের মাত্রা আর ভাষার একটা বেছে নিন।

মাত্রা

দুটি ভেক্টরের ডট প্রোডাক্ট নির্ভর করে তাদের দৈর্ঘ্য সমান হওয়ার উপর।

সেই সূত্রে, ম্যাট্রিক্স গুণের ক্ষেত্রে বাম ম্যাট্রিক্সের কলামের সংখ্যা আর ডান ম্যাট্রিক্সের সারির সংখ্যা মিলতে হবে।

সাইজগুলোকে size(A)-এর আউটপুটের মতো (nrows, ncols) টাপল হিসেবে লিখলে আমরা পাই (a, b) * (b, c) -> (a, c)। "ভেতরের" মাত্রাগুলো, এখানে b আর b, ডট প্রোডাক্ট নেওয়ার সাথে সামঞ্জস্যপূর্ণ। "বাইরের" মাত্রাগুলো, এখানে a আর c, আউটপুটের মাত্রা নির্ধারণ করে।

আয়তাকার ম্যাট্রিক্সের একটি উদাহরণ:

julia> D = reshape(1:6, 2, 3)
2×3 reshape(::UnitRange{Int64}, 2, 3) with eltype Int64:
 1  3  5
 2  4  6

julia> E = reshape(1:12, 3, 4)
3×4 reshape(::UnitRange{Int64}, 3, 4) with eltype Int64:
 1  4  7  10
 2  5  8  11
 3  6  9  12

julia> D * E
2×4 Matrix{Int64}:
 22  49   76  103
 28  64  100  136

# (3, 4) * (2, 3) not possible
julia> E * D
ERROR: DimensionMismatch: matrix A has axes (Base.OneTo(3),Base.OneTo(4)), matrix B has axes (Base.OneTo(2),Base.OneTo(3))

ম্যাট্রিক্সের মতো করে জোড়া ভেক্টর গুণ করার দুটি সম্ভাবনা আছে।

প্রচলিত নিয়মে আমরা ডট প্রোডাক্টের সমতুল্য হিসেবে u' * v ব্যবহার করব। মাত্রা হয় (1, 3) * (3, 1), আর Julia (1, 1) আউটপুটটিকে একটি স্কেলারে সরল করে দেয় (যেমন R করে না)।

বিকল্পভাবে আমরা u * v' ব্যবহার করতে পারি, যার মাত্রা (3, 1) * (1, 3) -> (3, 3), যা এলিমেন্টের সব সম্ভাব্য জোড়া গুণ করে ভেক্টর দুটিকে একটি ম্যাট্রিক্সে বিস্তার করে।

julia> u = [1, 2]
2-element Vector{Int64}:
 1
 2
julia> v = [3, 4]
2-element Vector{Int64}:
 3
 4
julia> u' * v
11
julia> u * v'
2×2 Matrix{Int64}:
 3  4
 6  8

u' * v-কে কখনও কখনও ইনার প্রোডাক্ট বলা হয়।

(কম কমন) u * v' সেই অনুপাতে আউটার প্রোডাক্ট। এটি টেনসর প্রোডাক্ট-এর সাথে সম্পর্কিত, যদিও সেটি আমাদের আওতার অনেক বাইরে।

রোটেশন

বিশেষভাবে কমন এক ধরনের ম্যাট্রিক্স গুণে থাকে রোটেশন ম্যাট্রিক্স।

2D-তে একটি ভেক্টরকে θ রেডিয়ান ঘড়ির কাঁটার বিপরীতে ঘোরানোর জন্য তুলনামূলক সরল একটি ম্যাট্রিক্স আছে।

julia> rot2d(θ, vec) = [cos(θ) -sin(θ); sin(θ) cos(θ)] * vec
rot2d (generic function with 1 method)

# unit vector in the x direction
julia> i_hat = [1, 0]
2-element Vector{Int64}:
 1
 0

# rotate 45 degrees
julia> rot2d(π/4, i_hat)
2-element Vector{Float64}:
 0.7071067811865476
 0.7071067811865475

# rotate 90 degrees -> unit vector in the y direction, j_hat
julia> rot2d(π/2, i_hat)
2-element Vector{Float64}:
 6.123233995736766e-17  # zero, within numerical error
 1.0

3D-তে রোটেশনের জন্য দুটি কোণযুক্ত আরও জটিল একটি ম্যাট্রিক্স লাগে। অনেক LaTeX না বসিয়ে এটি Markdown ডকুমেন্টে দেখানো কঠিন, তাই ফর্মুলার জন্য Wikipedia দেখুন।

OpenGL আর তার পরবর্তীদের মতো 3-D গ্রাফিক্সে রীতি হলো হোমোজিনিয়াস কোঅর্ডিনেট নিয়ে কাজ করা।

প্রতিটি ভার্টেক্স একটি 4-ভেক্টর দ্বারা প্রকাশ করা হয় (বা সমতুল্যভাবে একটি ম্যাট্রিক্স কলাম): (x, y, z) বিন্দুর জন্য [x, y, z, 1.0]।

এতে আরও বিস্তৃত ট্রান্সফর্মেশন ম্যাট্রিক্স সম্ভব হয়। রোটেশন থাকে আগের মতোই A[1:3, 1:3]-এ, ট্রান্সলেশন থাকে A[1:3, 4]-এ [Δx, Δy, Δz] হিসেবে, স্কেলিং থাকে কর্ণে, আর skew, perspective ইত্যাদির জন্য আরও সম্ভাবনা আছে।

পারফরম্যান্স

পৃথিবীজুড়ে CS বিভাগগুলোতে অনেক পিএইচডি থিসিস আছে, যার এক বা একাধিক অধ্যায় ম্যাট্রিক্স গুণের অ্যালগরিদমে ছোট ছোট ধাপে ধাপে উন্নতি নিয়ে। এটি সত্যিই গুরুত্বপূর্ণ, আর নানা প্রতিষ্ঠান নিজেদের স্বার্থে এই গবেষণায় অর্থায়ন করতে রাজি।

পারফরম্যান্স একটি বড় বিষয়, যার গভীরে আমরা যেতে পারব না, তবে উদাহরণ হিসেবে আমরা নানা সাইজের র্যান্ডম ম্যাট্রিক্স গুণ করে দেখতে পারি।

নিচের কোডটি একটি দ্রুত আর মোটামুটি হিসাব (BenchmarkTools.jl ব্যবহার করুন আরও ভালো পদ্ধতির জন্য)।

ব্যবহৃত সিস্টেমটি ছিল একটি ছোট $430 (মার্কিন) পিসি: Ryzen 9 প্রসেসর, 32GB RAM, Linux Mint 22.1, Julia 1.11.6।

julia> mmul(A) = A * A
mmul (generic function with 1 method)
julia> A = rand(Float64, 1_000, 1_000);
julia> @time mmul(A);
  0.011055 seconds (3 allocations: 7.629 MiB)
julia> A = rand(Float64, 10_000, 10_000);
julia> @time mmul(A);
  7.236284 seconds (1.61 k allocations: 763.027 MiB, 17.92% gc time, 0.15% compilation time)

মোটামুটি, দশ লাখ এলিমেন্টের এক জোড়া ম্যাট্রিক্স নিয়েছিল কয়েক মিলিসেকেন্ড, ১০ কোটি এলিমেন্টের ম্যাট্রিক্স নিয়েছিল কয়েক সেকেন্ড। আরও কয়েকটি মাত্রার ক্রম যোগ করতে হলে উন্নত হার্ডওয়্যার লাগবে...